{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:46Z","timestamp":1742617186674,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":56,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578116"},{"type":"electronic","value":"9783540483373"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57811-0_4","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:24:18Z","timestamp":1330262658000},"page":"33-39","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Some open problems in approximation"],"prefix":"10.1007","author":[{"given":"Mihalis","family":"Yannakakis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, \u201cProof Verification and Hardness of Approximation Problems\u201d, Proc. 33rd IEEE Symp. on Foundations of Computer Science, 14\u201323, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, S. Safra, \u201cProbabilistic Checking of Proofs\u201d, Proc. 33rd IEEE Symp. on Foundations of Computer Science, 2\u201313, 1992.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0304-3975(80)90006-7","volume":"12","author":"G. Ausiello","year":"1980","unstructured":"G. Ausiello, A. Marchetti-Spaccamela, M. Protasi, \u201cToward a Unified Approach for the Classification of NP-complete Optimization Problems\u201d, Theoretical Computer Science 12, 83\u201396, 1980.","journal-title":"Theoretical Computer Science"},{"key":"4_CR4","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/0022-0000(80)90046-X","volume":"21","author":"G. Ausiello","year":"1980","unstructured":"G. Ausiello, A. D'Atri, M. Protasi, \u201cStructure Preserving Reductions Among Convex Optimization Problems\u201d, J. Computer and System Sci. 21, 136\u2013153, 1980.","journal-title":"J. Computer and System Sci."},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"L. Babai, \u201cTransparent Proofs and Limits to Approximation\u201d, manuscript, 1993.","DOI":"10.1007\/978-3-0348-9110-3_2"},{"key":"4_CR6","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R. Bar-Yehuda","year":"1981","unstructured":"R. Bar-Yehuda, S. Even, \u201cA Linear Time Approximation Algorithm for the Weighted Vertex Cover Problem\u201d, J. Algorithms 2, 198\u2013203, 1981.","journal-title":"J. Algorithms"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund, A. Russel, \u201cEfficient Probabilistically Checkable Proofs and Applications to Approximation\u201d, Proc. 25th ACM Symp. on Theory of Computing, 294\u2013304, 1993.","DOI":"10.1145\/167088.167174"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"M. Bellare, P. Rogoway, \u201cThe Complexity of Approximating a Nonlinear Program\u201d, in Complexity in Numerical Optimization, P. Pardalos ed., WorldScientific, 1993.","DOI":"10.1142\/9789814354363_0002"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"M. Bellare, M. Sudan, \u201cImproved Non-Approximability Results\u201d, draft, Nov. 1993.","DOI":"10.1145\/195058.195129"},{"key":"4_CR10","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P. Berman","year":"1992","unstructured":"P. Berman, G. Schnitger, \u201cOn the Complexity of Approximating the Independent Set Problem\u201d, Information and Computation 96, 77\u201394, 1992.","journal-title":"Information and Computation"},{"key":"4_CR11","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M. Bern","year":"1989","unstructured":"M. Bern, P. Plassman, \u201cThe Steiner Problem with Edge Lengths 1 and 2\u201d, Information Processing Letters, 32, 171\u2013176, 1989.","journal-title":"Information Processing Letters"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"A. Blum, \u201cSome Tools for Approximate 3-coloring\u201d, Proc. 30th IEEE Symp. on Foundations of Computer Science, 554\u2013562, 1990.","DOI":"10.1109\/FSCS.1990.89576"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"A. Blum, T. Jiang, M. Li, J. Tromp, M. Yannakakis, \u201cLinear Approximation of Shortest Superstrings\u201d, Proc. 23rd Annual ACM Symp. on Theory of Computing, 328\u2013336, 1991.","DOI":"10.1145\/103418.103455"},{"key":"4_CR14","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0890-5401(91)90025-W","volume":"93","author":"P. Crescenzi","year":"1991","unstructured":"P. Crescenzi, A. Panconesi, \u201cCompleteness in Approximation Classes\u201d, Information and Computation 93, 241\u2013262, 1991.","journal-title":"Information and Computation"},{"key":"4_CR15","volume-title":"Technical Report","author":"N. Christofides","year":"1976","unstructured":"N. Christofides, \u201cWorst-case Analysis of New Heuristics For the Traveling Salesman Problem\u201d, Technical Report, GSIA, Carnegie-Mellon, 1976."},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. Seymour, M. Yannakakis, \u201cThe Complexity of Multiway Cuts\u201d, Proc. 24th Annual ACM Symp. on Theory of Computing, 1992.","DOI":"10.1145\/129712.129736"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"U. Feige, J. Kilian, \u201cTwo Prover Protocols \u2014 Low Error at Affordable Rate\u201d, draft, Oct. 1993.","DOI":"10.1145\/195058.195128"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"U. Feige, L. Lovasz, \u201cTwo-prover One-round Proof Systems: Their Power and Their Problems\u201d, Proc. 24th Annual ACM Symp. on Theory of Computing, 733\u2013744, 1992.","DOI":"10.1145\/129712.129783"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lovasz, S. Safra, M. Szegedy, \u201cApproximating Clique is Almost NP-complete\u201d, Proc. 32nd IEEE Symp. on Foundations of Computer Science, 2\u201312, 1991.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"4_CR20","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/net.3230120103","volume":"12","author":"A. M. Frieze","year":"1982","unstructured":"A. M. Frieze, G. Galbiati, F. Maffioli, \u201cOn the Worst-case Performance of Some Algorithms for the Asymmetric Traveling Salesman Problem\u201d, Networks 12, 23\u201339, 1982.","journal-title":"Networks"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"N. Garg, V. V. Vazirani, M. Yannakakis, \u201cApproximate Max-Flow Min-(Multi)cut Theorems and Their Applications\u201d, Proc. 25th Annual ACM Symp. on Theory of Computing, pp. 698\u2013707, 1992.","DOI":"10.1145\/167088.167266"},{"key":"4_CR22","unstructured":"M. X. Goemans, D. P. Williamson, \u201cA New 3\/4 Approximation Algorithm for MAX SAT\u201d, Proc. 3rd Conf. on Integer Programming and Combinatorial Optimization, 1993."},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"M. X. Goemans, D. P. Williamson, \u201c.878 Approximation Algorithms for MAX CUT and MAX 2SAT\u201d, draft, Nov. 1993.","DOI":"10.1145\/195058.195216"},{"key":"4_CR24","unstructured":"M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, 1979."},{"key":"4_CR25","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0020-0190(86)90068-2","volume":"22","author":"D. Gusfield","year":"1986","unstructured":"D. Gusfield, L. Pitt, \u201cEquivalent Approximation Algorithms for Node Cover\u201d, Information Processing Letters 22, 291\u2013294, 1986.","journal-title":"Information Processing Letters"},{"key":"4_CR26","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"M. Held, R. M. Karp, \u201cThe Traveling Salesman Problem and Minimum Spanning Trees\u201d, Operations Research 18, 1138\u20131162, 1970.","journal-title":"Operations Research"},{"key":"4_CR27","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0166-218X(83)90080-X","volume":"6","author":"D. S. Hochbaum","year":"1982","unstructured":"D. S. Hochbaum, \u201cEfficient Bounds for the Stable Set, Vertex Cover, and Set Packing Problems\u201d, Discrete Applied Mathematics 6, 243\u2013254, 1982.","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR28","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/0020-0190(91)90188-N","volume":"37","author":"R. W. Irving","year":"1991","unstructured":"R. W. Irving, \u201cOn Approximating the Minimum Independent Dominating Set\u201d, Information Processing Letters 37, 197\u2013200, 1991.","journal-title":"Information Processing Letters"},{"key":"4_CR29","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. S. Johnson","year":"1974","unstructured":"D. S. Johnson, \u201cApproximation Algorithms for Combinatorial Problems\u201d, J. Comp. Sys. Sc. 9, 256\u2013278, 1974.","journal-title":"J. Comp. Sys. Sc."},{"key":"4_CR30","unstructured":"D. S. Johnson, \u201cWorst Case Behavior of Graph Coloring Algorithms\u201d, Proc. 5th Conf. on Combinatorics, Graph Theory and Computing, 513\u2013527, 1974."},{"key":"4_CR31","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1016\/0196-6774(92)90052-E","volume":"13","author":"D. S. Johnson","year":"1992","unstructured":"D. S. Johnson, \u201cThe NP-completeness Column: An Ongoing Guide\u201d, J. of Algorithms 13, 502\u2013524, 1992.","journal-title":"J. of Algorithms"},{"key":"4_CR32","volume-title":"Ph.D. Thesis","author":"V. Kann","year":"1992","unstructured":"V. Kann, \u201cOn the Approximability of NP-complete Optimization Problems\u201d, Ph.D. Thesis, Royal Institute of Technology, Stockholm, 1992."},{"key":"4_CR33","doi-asserted-by":"crossref","unstructured":"R. M. Karp, \u201cReducibility among Combinatorial Problems\u201d, in R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, 85\u2013103, 1972.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"4_CR34","doi-asserted-by":"crossref","unstructured":"P. Klein, A. Agrawal, R. Ravi, S. Rao, \u201cApproximation Through Multicommodity Flow\u201d, Proc. 31st Annual IEEE Symp. on Foundations of Computer Science, 726\u2013737, 1990.","DOI":"10.1109\/FSCS.1990.89595"},{"key":"4_CR35","doi-asserted-by":"crossref","unstructured":"S. Khanna, N. Linial, S. Safra, \u201cOn the Hardness of Approximating the Chromatic Number\u201d, Proc. 2nd Israel Symp. on Theory and Computing Sys., 250\u2013260, 1993.","DOI":"10.1109\/ISTCS.1993.253464"},{"key":"4_CR36","unstructured":"S. Khanna, R. Motwani, M. Sudan, U. Vazirani, \u201cOn Syntactic versus Computational Views of Approximation\u201d, draft, Nov. 1993."},{"key":"4_CR37","doi-asserted-by":"crossref","unstructured":"P. G. Kolaitis, M,. N. Thakur, \u201cApproximation Properties of NP Minimization Classes\u201d, Proc. 6th Conf. on Structures in Computer Science, 353\u2013366, 1991.","DOI":"10.1109\/SCT.1991.160280"},{"key":"4_CR38","doi-asserted-by":"crossref","unstructured":"D. Lapidot, A. Shamir, \u201cFully Parallelized Multiprover Protocols for NEXP-TIME\u201d, Proc. 32nd Annual IEEE Symp. on Foundations of Computer Science, 13\u201318, 1991.","DOI":"10.1109\/SFCS.1991.185342"},{"key":"4_CR39","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnoy Kan, D. B. Shmoys, The Traveling Salesman Problem, J. Wiley & Sons, 1985."},{"key":"4_CR40","doi-asserted-by":"crossref","unstructured":"F. T. Leighton, S. Rao, \u201cAn Approximate Max-flow Min-cut Theorem for Uniform Multicommodity Flow Problems with Applications to Approximation Algorithms\u201d, Proc. 28th Annual IEEE Symp. on Foundations of Computer Science, 256\u2013269, 1988. Full (unpublished) version has additional results.","DOI":"10.21236\/ADA211908"},{"key":"4_CR41","doi-asserted-by":"crossref","unstructured":"C. Lund, M. Yannakakis, \u201cOn the Hardness of Approximating Minimization Problems\u201d, Proc. 25th ACM Symp. on Theory of Computing, 286\u2013293, 1993.","DOI":"10.1145\/167088.167172"},{"key":"4_CR42","doi-asserted-by":"crossref","unstructured":"C. Lund, M. Yannakakis, \u201cThe Approximation of Maximum Subgraph Problems\u201d, Proc. 20th Intl. Coll. on Automata, Languages and Programming, 40\u201351, 1993.","DOI":"10.1007\/3-540-56939-1_60"},{"key":"4_CR43","doi-asserted-by":"crossref","unstructured":"A. Panconesi, D. Ranjan, \u201cQuantifiers and Approximation\u201d, Proc. 22nd ACM Symp. They of Computing, 446\u2013456, 1990.","DOI":"10.1145\/100216.100275"},{"key":"4_CR44","unstructured":"C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1993."},{"key":"4_CR45","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"C. H. Papadimitriou, M. Yannakakis, \u201cOptimization, Approximation and Complexity Classes\u201d, J. Computer and System Sci. 43, 425\u2013440, 1991.","journal-title":"J. Computer and System Sci."},{"key":"4_CR46","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C. H. Papadimitriou","year":"1993","unstructured":"C. H. Papadimitriou, M. Yannakakis, \u201cThe Traveling Salesman Problem with Distances One and Two\u201d, Mathematics of Operations Research 18, 1\u201311, 1993.","journal-title":"Mathematics of Operations Research"},{"key":"4_CR47","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0304-3975(81)90081-5","volume":"15","author":"A. Paz","year":"1981","unstructured":"A. Paz, S. Moran, \u201cNon Deterministic Polynomial Optimization Problems and their Approximation\u201d, Theoretical Computer Science 15, 251\u2013277, 1981.","journal-title":"Theoretical Computer Science"},{"key":"4_CR48","doi-asserted-by":"crossref","unstructured":"S. Plotkin, E. Tardos, \u201cImproved Bounds on the Max-Flow Min-Cut Ratio for Multicommodity Flow Problems\u201d, Proc. 25th Annual ACM Symp. on Theory of Computing, 691\u2013697, 1993.","DOI":"10.1145\/167088.167263"},{"key":"4_CR49","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"S. Sahni, T. Gonzalez, \u201cP-complete Approximation Problems\u201d, J. ACM 23, 555\u2013565, 1976.","journal-title":"J. ACM"},{"key":"4_CR50","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/0020-0190(82)90022-9","volume":"14","author":"C. Savage","year":"1982","unstructured":"C. Savage, \u201cDepth-first Search and the Vertex Cover Problem\u201d, Information Processing Letters 14, 233\u2013235, 1982.","journal-title":"Information Processing Letters"},{"key":"4_CR51","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(90)90028-V","volume":"35","author":"D. B. Shmoys","year":"1990","unstructured":"D. B. Shmoys, D. P. Williamson, \u201cAnalyzing the Held-Karp TSP bound: A Monotonicity Property with Application\u201d, Information Processing Letters 35, 281\u2013285, 1990.","journal-title":"Information Processing Letters"},{"key":"4_CR52","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0167-6377(92)90068-E","volume":"12","author":"D. P. Williamson","year":"1992","unstructured":"D. P. Williamson, \u201cAnalysis of the Held-Karp Lower Bound for the Assymetric TSP\u201d, Operations Research Letters 12, 83\u201388, 1992.","journal-title":"Operations Research Letters"},{"key":"4_CR53","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BFb0120913","volume":"13","author":"L. A. Wolsey","year":"1980","unstructured":"L. A. Wolsey, \u201cHeuristic Analysis, Linear Programming and Branch and Bound\u201d, Mathematical Programming Study 13, 121\u2013134, 1980.","journal-title":"Mathematical Programming Study"},{"key":"4_CR54","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1145\/322154.322157","volume":"26","author":"M. Yannakakis","year":"1979","unstructured":"M. Yannakakis, \u201cThe Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems\u201d, J.ACM 26, 618\u2013630, 1979.","journal-title":"J.ACM"},{"key":"4_CR55","unstructured":"M. Yannakakis, \u201cOn the Approximation of Maximum Satisfiability\u201d, Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, 1\u20139, 1992."},{"key":"4_CR56","doi-asserted-by":"crossref","unstructured":"D. Zuckerman, \u201cNP-complete Problems Have a Version That's Hard to Approximate\u201d, Proc. 8th Conf. on Structure in Complexity Theory, 305\u2013312, 1993.","DOI":"10.1109\/SCT.1993.336517"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57811-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:13:51Z","timestamp":1742595231000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57811-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578116","9783540483373"],"references-count":56,"URL":"https:\/\/doi.org\/10.1007\/3-540-57811-0_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"26 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}