{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:21Z","timestamp":1759637601563,"version":"3.30.1"},"reference-count":27,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2002,10,1]],"date-time":"2002-10-01T00:00:00Z","timestamp":1033430400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3942,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2002,10]]},"DOI":"10.1016\/s0304-3975(01)00343-7","type":"journal-article","created":{"date-parts":[[2002,10,7]],"date-time":"2002-10-07T20:25:18Z","timestamp":1034022318000},"page":"553-571","source":"Crossref","is-referenced-by-count":10,"title":["The inapproximability of non-NP-hard optimization problems"],"prefix":"10.1016","volume":"289","author":[{"given":"Liming","family":"Cai","sequence":"first","affiliation":[]},{"given":"David","family":"Juedes","sequence":"additional","affiliation":[]},{"given":"Iyad","family":"Kanj","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(01)00343-7_BIB1","unstructured":"S. Arora, Personal communication."},{"key":"10.1016\/S0304-3975(01)00343-7_BIB2","series-title":"Approximation Algorithms for NP-hard problems","first-page":"399","article-title":"Hardness of approximations","author":"Arora","year":"1997"},{"key":"10.1016\/S0304-3975(01)00343-7_BIB3","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sundar, M. Szegedy, Verification and hardness of approximation problems, in: Proc. 33rd Ann. IEEE Symp. on Foundations of Computer Science, Los Alamitos, CA, IEEE Computer Society Press, Silver Spring, MD, 1992, pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"10.1016\/S0304-3975(01)00343-7_BIB4","doi-asserted-by":"crossref","unstructured":"S. Arora, S. Safra, Probabilistic checking of proofs, in: Proc. 33rd Ann. Symp. on Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, 1992, pp. 2\u201313.","DOI":"10.1109\/SFCS.1992.267824"},{"year":"1999","series-title":"Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties","author":"Ausiello","key":"10.1016\/S0304-3975(01)00343-7_BIB5"},{"key":"10.1016\/S0304-3975(01)00343-7_BIB6","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund, A. Russell, Efficient probabilistic checking of proofs and applications to approximation, in: Proc. 25th Ann. ACM Symp. on the Theory of Computing, New York, 1993, ACM Press, New York, pp. 294\u2013304.","DOI":"10.1145\/195058.195467"},{"key":"10.1016\/S0304-3975(01)00343-7_BIB7","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BF01994876","article-title":"Approximating maximum independent sets by excluding subgraphs","volume":"32","author":"Boppana","year":"1992","journal-title":"BIT"},{"key":"10.1016\/S0304-3975(01)00343-7_BIB8","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1137\/0222038","article-title":"Nondeterminism within P","volume":"22","author":"Buss","year":"1993","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/S0304-3975(01)00343-7_BIB9","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1006\/jcss.1997.1490","article-title":"On fixed-parameter tractability and approximability of NP optimization problems","volume":"54","author":"Cai","year":"1997","journal-title":"J. Comput. System Sci."},{"issue":"3","key":"10.1016\/S0304-3975(01)00343-7_BIB10","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/S0097539793258295","article-title":"On the amount of nondeterminism and the power of verifier","volume":"26","author":"Cai","year":"1997","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(01)00343-7_BIB11","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1006\/inco.1995.1156","article-title":"On the structure of parameterized problems in NP","volume":"123","author":"Cai","year":"1995","journal-title":"Inform. Comput."},{"key":"10.1016\/S0304-3975(01)00343-7_BIB12","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BF02090764","article-title":"Classes of bounded nondeterminism","volume":"23","author":"D\u0131\u0301az","year":"1990","journal-title":"Math. System Theory"},{"key":"10.1016\/S0304-3975(01)00343-7_BIB13","doi-asserted-by":"crossref","unstructured":"R.G. Downey, M.R. Fellows, Fixed-parameter intractability, in: Proc. Seventh Ann. Conf. Structure in Complexity Theory, Boston, MA, USA, IEEE Computer Society Press, Silver Spring, MD, 1992, pp. 36\u201349.","DOI":"10.1109\/SCT.1992.215379"},{"issue":"4","key":"10.1016\/S0304-3975(01)00343-7_BIB14","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1137\/S0097539792228228","article-title":"Fixed-parameter tractability and completeness I: Basic results","volume":"24","author":"Downey","year":"1995","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(01)00343-7_BIB15","doi-asserted-by":"crossref","unstructured":"R.G. Downey, M.R. Fellows, Parameterized computational feasibility, in: FEASMATH: Feasible Mathematics: A Mathematical Sciences Institute Workshop, Birkhauser, 1995.","DOI":"10.1007\/978-1-4612-2566-9_7"},{"key":"10.1016\/S0304-3975(01)00343-7_BIB16","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/BF01178668","article-title":"On problems with short certificates","volume":"31","author":"Farr","year":"1994","journal-title":"Acta Inform."},{"key":"10.1016\/S0304-3975(01)00343-7_BIB17","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, S. Safra, M. Szegedy, Approximating clique is almost NP-complete, in: Proc. 32nd IEEE Symp. on the Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, 1991, pp. 2\u201312.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"10.1016\/S0304-3975(01)00343-7_BIB18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/cjtcs.1997.001","article-title":"On limited versus polynomial nondeterminism","volume":"1997","author":"Feige","year":"1997","journal-title":"Chicago J. Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00343-7_BIB19","doi-asserted-by":"crossref","unstructured":"U. Feige, A threshold of lnn for approximating set cover (preliminary version), in: Proc. 28th Ann. ACM Symp. on the Theory of Computing, Philadelphia, Pennsylvania, 22\u201324 May 1996, pp. 314\u2013318.","DOI":"10.1145\/237814.237977"},{"key":"10.1016\/S0304-3975(01)00343-7_BIB20","doi-asserted-by":"crossref","unstructured":"D. Fotakis, P. Spirakis, (poly(loglogn), poly(loglogn))-restricted verifiers are unlikely to exist for languages in NP, in: Proc. 23nd Internat. Symp. on Mathematical Foundations of Computer Science, Springer, Berlin, 1996, pp. 360\u2013371.","DOI":"10.1007\/3-540-61550-4_162"},{"issue":"2","key":"10.1016\/S0304-3975(01)00343-7_BIB21","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1145\/235767.235769","article-title":"Guest column: Limited nondeterminism","volume":"27","author":"Goldsmith","year":"1996","journal-title":"SIGACT News"},{"key":"10.1016\/S0304-3975(01)00343-7_BIB22","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","article-title":"Approximation algorithms for combinatorial problems","volume":"9","author":"Johnson","year":"1974","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/S0304-3975(01)00343-7_BIB23","unstructured":"V. Kann, On the Approximability of NP-complete Optimization Problems, Ph.D. Thesis, Royal Institute of Technology, Sweden, 1992."},{"key":"10.1016\/S0304-3975(01)00343-7_BIB24","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0304-3975(88)90131-4","article-title":"On finding a minimum dominating set in a tournament","volume":"61","author":"Megiddo","year":"1988","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(01)00343-7_BIB25","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou, M. Yannakakis, On limited nondeterminism and the complexity of the V\u2013C dimension, in: Proc. Eigth Ann. Conf. on Structure in Complexity Theory (SCTC \u201993), San Diego, CA, USA, IEEE Computer Society Press, Silver Spring, MD, 1993, pp. 12\u201318.","DOI":"10.1109\/SCT.1993.336545"},{"key":"10.1016\/S0304-3975(01)00343-7_BIB26","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad, Clique is hard to approximate within n1\u2212\u03b5, in: Proc. 37th Ann. IEEE Symp. on Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, 1996, pp. 627\u2013636.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"10.1016\/S0304-3975(01)00343-7_BIB27","unstructured":"R. Szelepcs\u00e9nyi, \u03b2k-complete problems and greediness, Tech. Rep. 445, Computer Science Department, University, Rochester, NY, 1993."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501003437?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397501003437?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T08:18:09Z","timestamp":1733818689000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397501003437"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,10]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,10]]}},"alternative-id":["S0304397501003437"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(01)00343-7","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[2002,10]]}}}