{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T15:45:53Z","timestamp":1772552753336,"version":"3.50.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1994,6,1]],"date-time":"1994-06-01T00:00:00Z","timestamp":770428800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1994,6]]},"DOI":"10.1007\/bf01202286","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T15:52:58Z","timestamp":1108741978000},"page":"133-157","source":"Crossref","is-referenced-by-count":134,"title":["The hardness of approximation: Gap location"],"prefix":"10.1007","volume":"4","author":[{"given":"Erez","family":"Petrank","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, Recursive Construction for 3-Regular Expanders. InProc. 28th Ann. Symp. Found. Comput. Sci., 1987, 295?304.","DOI":"10.1109\/SFCS.1987.50"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"N. Alon, R. A. Duke, H. Lefmann, V. R\u00f6dl, and R. Yuster, The Algorithmic Aspects of the Regularity Lemma. InProc. 33th Ann. Symp. Found. Comput. Sci., 1992, 473?482.","DOI":"10.1109\/SFCS.1992.267804"},{"key":"CR3","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra, Probabilistic Checking of Proofs: A New Characterization of NP. InProc. 33th Ann. Symp. Found. Comput. Sci., 1992, 1?13.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof Verification and Intractability of Approximation Problems. InProc. 33th Ann. Symp. Found. Comput. Sci., 1992, 14?23.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"CR5","unstructured":"M. Bellare and E. Petrank, private communication, 1992."},{"key":"CR6","volume-title":"Graph and Hypergraphs","author":"C. Berge","year":"1973","unstructured":"C. Berge,Graph and Hypergraphs. North-Holland, Amsterdam, 1973."},{"key":"CR7","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 andP. Plassmann, The Steiner problem with edge lengths 1 and 2.Inform. Process. Lett. 32 (1989), 171?176.","journal-title":"Inform. Process. Lett."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"A. Blum, T. Jiang, M. Li, J. Tromp, and M. Yannakakis, Linear Approximation of Shortest Superstrings. InProc. 31th Ann. Symp. Found. Comput. Sci., 1990, 554?562.","DOI":"10.1145\/103418.103455"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis, The Complexity of Multiway Cuts. InProc. Twenty-forth Ann. ACM Symp. Theor. Comput., 1992, 241?251.","DOI":"10.1145\/129712.129736"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, S. Safra, and M. Szegedy, Approximating clique is almost NP-complete. InProc. 32th Ann. Symp. Found. Comput. Sci., 1991, 2?12.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","volume":"22","author":"O. Gabber","year":"1981","unstructured":"O. Gabber andZ. Galil, Explicit Construction of linear sized superconcentrators.J. Comput. System Sci. 22 (1981), 407?420.","journal-title":"J. Comput. System Sci."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/321921.321926","volume":"23","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey andD. S. Johnson, The complexity of near-optimal graph coloring.J. Assoc. Comput. Mach. 23 (1976), 43?49.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR13","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979."},{"key":"CR14","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, D. S. Johnson, andL. J. Stockmeyer, Some Simplified NP-Complete Graph Problems.Theoret. Comput. Sci. 1 (1976), 237?267.","journal-title":"Theoret. Comput. Sci."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"J. Hastad, S. Phillips, and S. Safra, A well Characterized Approximation Problem. InProceedings of the 2nd Israel Symposium on Theory of Computing and Systems, 1993, 261?265.","DOI":"10.1109\/ISTCS.1993.253463"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Hoyler","year":"1981","unstructured":"I. Hoyler, The NP-Competeness of Edge Coloring.SIAM J. Comput. 10 (1981), 718?720.","journal-title":"SIAM J. Comput."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V. Kann","year":"1991","unstructured":"V. Kann Maximum Bounded 3-Dimensional Matching is MAX SNP-Complete.Inform. Process. Lett. 37 (1991), 27?35.","journal-title":"Inform. Process. Lett."},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"R. M. Karp, Reducibility among combinatorial problems. InComplexity of Computer Computations, ed.Raymond E. Miller and James W. Thatcher, Plenum Press, 1972, 85?103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0196-6774(83)90032-9","volume":"4","author":"D. Leven","year":"1983","unstructured":"D. Leven andZ. Galil, NP-completness of finding the chromatic index of regular graphs.J. Algorithms 4 (1983), 35?44.","journal-title":"J. Algorithms"},{"key":"CR20","unstructured":"L. Lov\u00e1sz, Coverings and Colorings of Hypergraphs. InProc. 4-th Southern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica Publishing, 1973, 3?12."},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis, On the Hardness of Approximating Minimization Problems. InProc. Twenty-fifth Ann. ACM Symp. Theor. Comput., 1993, 286?293.","DOI":"10.1145\/167088.167172"},{"key":"CR22","first-page":"71","volume":"9","author":"G. A. Margulis","year":"1973","unstructured":"G. A. Margulis, Explicit Constructions of Concentrators.Comm. ACM 9 (1973), 71?80. (English translation inProblems Inform. Transmission, 1975, 325?332.).","journal-title":"Comm. ACM"},{"key":"CR23","unstructured":"R. Motwani, Lecture Notes on Approximation Algorithms. Technical report, Dept. of Computer Science, Stanford University, 1992."},{"key":"CR24","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 andM. Yannakakis, Optimization, Approximation, and Complexity Classes.J. Comput. System Sci. 43 (1991), 425?440.","journal-title":"J. Comput. System Sci."},{"key":"CR25","doi-asserted-by":"crossref","unstructured":"C. H. Papadimitriou and M. Yannakakis, The Traveling Salesman Problem with Distances One and Two.Mathematics of Operations Research (to appear).","DOI":"10.1287\/moor.18.1.1"},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"E. Petrank, The Hardness of Approximation: Gap Location. InProceedings of the 2nd Israel Symposium on Theory of Computing and Systems, 1993, 275?284.","DOI":"10.1109\/ISTCS.1993.253461"},{"key":"CR27","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"S. Sahni andT. Gonzalez, P-complete approximation problems.J. Assoc. Comput. Mach. 23 (1976), 555?565.","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"CR28","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/1008293.1008294","volume":"5","author":"L. J. Stockmeyer","year":"1973","unstructured":"L. J. Stockmeyer, Planar 3-Colorability is NP-Complete.SIGACT News 5(3) (1973), 19?25.","journal-title":"SIGACT News"}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01202286.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01202286\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01202286","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T12:51:37Z","timestamp":1734958297000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01202286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,6]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1994,6]]}},"alternative-id":["BF01202286"],"URL":"https:\/\/doi.org\/10.1007\/bf01202286","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,6]]}}}