{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:17Z","timestamp":1742617157124,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540582182"},{"type":"electronic","value":"9783540485773"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58218-5_21","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:36:45Z","timestamp":1330270605000},"page":"231-239","source":"Crossref","is-referenced-by-count":0,"title":["Recent results in hardness of approximation"],"prefix":"10.1007","author":[{"given":"Johan","family":"H\u00e5stad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Arora S., Lund C., Motwani R., Sudan M, and M. Szegedy, \u201cProof verification and intractability of approximation problems.\u201d Proc. 33rd IEEE Symposium on Foundation of Computer Science, October 1992, pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Arora S. and Safra S. \u201cProbabilistic Checkable Proofs: A New Characterization of NP.\u201d Proc. 33rd IEEE Symposium on Foundation of Computer Science, October 1992, pp. 1\u201313.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"Babai L., Fortnow L, and Lund C. \u201cNon-deterministic Exponential time has Two-Prover Interactive Protocols Proc. 31st IEEE Symposium on Foundation of Computer Science, October 1990, pp. 16\u201325.","DOI":"10.1109\/FSCS.1990.89520"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"Babai L., Fortnow L, Levin L, and Szegedy M. \u201cChecking Computations in Polylogarithmic Time\u201d Proc 23rd ACM Symposium on theory of computation, May 1991, pp 21\u201331.","DOI":"10.1145\/103418.103428"},{"key":"21_CR5","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"Babai L. and Moran S. \u201cArthur-Merlin Games: A Randomized Proof System and a Hierarchy of Complexity Classes\u201d, Journal of Computer and System Sciences, Vol 36, pp 254\u2013276, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"Bellare M., Goldwasser S., Lund C., and Russell A. \u201cEfficient Probabilistically Checkable Proofs; Applications to Approximation\u201d, Proc 25th ACM Symposium on theory of computation, May 1993, pp 294\u2013304.","DOI":"10.1145\/167088.167174"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Bellare M. and Sudan M. \u201cImproved Non-Approximability Results\u201d, manuscript 1993, to appear at 26th ACM Symposium on theory of computation, May 1994.","DOI":"10.1145\/195058.195129"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Berman P. and Schnitger G. \u201cOn the Complexity of approximating the independent set problem\u201d, Proceedings of 6th Annual Symposium on Theoretical Aspects of Computer Science, pp 256\u2013268, 1989. Springer Verlag, Lecture Notes in Computer Science 349.","DOI":"10.1007\/BFb0028990"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Ben-Or M., Goldwasser S., Kilian J. and Wigderson A. \u201cMulti-Prover Interactive Proofs: How to remove Intractability\u201d, Proceeding 20th ACM Symposium on Theory of Computing, 1988, pp 113\u2013131.","DOI":"10.1145\/62212.62223"},{"key":"21_CR10","volume-title":"Technical report","author":"N. Christofides","year":"1976","unstructured":"Christofides N. \u201cWorst-case analysis of a new heuristic for the traveling salesman problem\u201d, Technical report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, 1976."},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Cook S. A. \u201cThe complexity of Theorem Proving Procedure.\u201d Proceeding 3rd ACM Symposium on Theory of Computing, 1971, pp 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Feige U., Goldwasser S., Lov\u00e1sz L, Safra S. and Szegedy M. \u201cApproximating Clique is Almost NP-complete\u201d Proc. 32nd IEEE Symposium on Foundation of Computer Science, October 1991, pp. 2\u201312.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Fortnow L., Rompel J. and Sipser M. \u201cOn the power of Multi-Prover Interactive Protocols\u201d Proceedings 3rd IEEE Symposium on Structure in Complexity Theory, pp 156\u2013161, 1988.","DOI":"10.1109\/SCT.1988.5275"},{"key":"21_CR14","unstructured":"Garey M. R. and Johnson D.S. \u201cComputers and intractability; a guide to the theory of NP-completeness\u201d, W.H. FREEMAN, 1979."},{"key":"21_CR15","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O. Goldreich","year":"1991","unstructured":"Goldreich O., Micali S., and Wigderson A. \u201cProofs that Yield Nothing but their Validity or All Languages in NP have Zero-Knowledge Proof System\u201d, Journal of ACM, Vol 38, 1991, pp 691\u2013729.","journal-title":"Journal of ACM"},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S. Goldwasser","year":"1989","unstructured":"Goldwasser S., Micali S. and Rackoff C. \u201cThe Knowledge Complexity of Interactive Proof Systems\u201d, SIAM Journal on Computing, Vol 18, pp 186\u2013208, 1989.","journal-title":"SIAM Journal on Computing"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Goldwasser S., and Sipser M. \u201cPrivate Coins versus Public Coins in Interactive Proof Systems, Proceeding 18th ACM Symposium on Theory of Computing, 1986, pp 59\u201368.","DOI":"10.1145\/12130.12137"},{"key":"21_CR18","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/0022-0000(91)90007-R","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Gurevich Y., \u201cAverage Case Completeness\u201d, Journal of Computer and System Sciences, Vol 42, 1991, pp 346\u2013398.","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR19","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D. Johnson","year":"1974","unstructured":"Johnson D. \u201cApproximation algorithms for combinatorial problems\u201d Journal of Computer and System Sciences, Vol 9, 1974, pp 256\u2013278.","journal-title":"Journal of Computer and System Sciences"},{"key":"21_CR20","unstructured":"Kann V. \u201cOn the approximability of NP-complete optimization problem\u201d, Ph. D. thesis, 1992, department of numerical analysis and computing science, Royal Institute of Technology."},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Karmarkar N. and Karp R. M. \u201cAn efficient approximation scheme for one-dimensional bin packing problem\u201d, Proc. 23rd IEEE Symposium on Foundation of Computer Science, 1982, pp. 312\u2013320.","DOI":"10.1109\/SFCS.1982.61"},{"key":"21_CR22","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"Levin, L. \u201cAverage Case Complete Problems\u201d SIAM Journal on Computing, Vol 15, 1986, pp 285\u2013286.","journal-title":"SIAM Journal on Computing"},{"key":"21_CR23","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L. Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz L. \u201cOn the ration of optimal integral and fractional covers\u201d Discrete mathematics, Vol 13, 1975, pp 383\u2013390.","journal-title":"Discrete mathematics"},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"Lund C., Fortnow L., Karloff H. and Nisan N. \u201cAlgebraic Methods for Interactive Proof Systems\u201d Proc. 31st IEEE Symposium on Foundation of Computer Science, October 1990, pp. 2\u201310.","DOI":"10.1109\/FSCS.1990.89518"},{"key":"21_CR25","doi-asserted-by":"crossref","unstructured":"Lund C. and Yannakakis M. \u201cOn the Hardness of Approximating Minimization Problems\u201d Proceeding 25th ACM Symposium on Theory of Computing, 1993, pp 59\u201368.","DOI":"10.1145\/167088.167172"},{"key":"21_CR26","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou C. and Yannakakis M. \u201cOptimization, approximation and complexity classes\u201d Journal of Computer and System Science, vol 43 pp 425\u2013440, 1991.","journal-title":"Journal of Computer and System Science"},{"key":"21_CR27","unstructured":"Shamir A. \u201cIP=PSPACE\u201d, Proc. 31st IEEE Symposium on Foundation of Computer Science, October 1990, pp. 11\u201315."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT '94"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58218-5_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:23:35Z","timestamp":1742595815000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58218-5_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540582182","9783540485773"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-58218-5_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}