{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,15]],"date-time":"2025-11-15T10:04:51Z","timestamp":1763201091257},"reference-count":50,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[1995,10,1]],"date-time":"1995-10-01T00:00:00Z","timestamp":812505600000},"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":6499,"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":[[1995,10]]},"DOI":"10.1016\/0304-3975(94)00291-p","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T16:19:56Z","timestamp":1027613996000},"page":"1-55","source":"Crossref","is-referenced-by-count":76,"title":["Approximate solution of NP optimization problems"],"prefix":"10.1016","volume":"150","author":[{"given":"G.","family":"Ausiello","sequence":"first","affiliation":[]},{"given":"P.","family":"Crescenzi","sequence":"additional","affiliation":[]},{"given":"M.","family":"Protasi","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(94)00291-P_BIB1","series-title":"Proc. 33-rd Ann. IEEE Symp. on Foundations of Computer Science","first-page":"14","article-title":"Proof verification and hardness of approximation problems","author":"Arora","year":"1992"},{"key":"10.1016\/0304-3975(94)00291-P_BIB2","series-title":"Proc: 33rd Ann. IEEE Symp. on Foundations of Computer Science","first-page":"2","article-title":"Probabilistic checking of proofs: a new characterization of NP","author":"Arora","year":"1992"},{"key":"10.1016\/0304-3975(94)00291-P_BIB3","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/0022-0000(80)90046-X","article-title":"Structure preserving reductions among convex optimization problems","volume":"21","author":"Ausiello","year":"1980","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/0304-3975(94)00291-P_BIB4","doi-asserted-by":"crossref","first-page":"83","DOI":"10.3233\/FI-1981-4105","article-title":"Lattice theoretic properties of NP-complete problems","volume":"4","author":"Ausiello","year":"1981","journal-title":"Fundamenta Informaticae"},{"key":"10.1016\/0304-3975(94)00291-P_BIB5","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/0304-3975(80)90006-7","article-title":"Toward a unified approach for the classification of NP-complete optimization problems","volume":"12","author":"Ausiello","year":"1980","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(94)00291-P_BIB6","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0020-0190(95)00006-X","article-title":"Local search, reducibility, and approximability of NP optimization problems","volume":"54","author":"Ausiello","year":"1995","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(94)00291-P_BIB7","series-title":"Proc. 23-rd Ann. ACM Symp. on Theory of Computing","first-page":"21","article-title":"Checking computations in polylogarithmic time","author":"Babai","year":"1991"},{"key":"10.1016\/0304-3975(94)00291-P_BIB8","series-title":"Structural Complexity I","author":"Balcazar","year":"1988"},{"key":"10.1016\/0304-3975(94)00291-P_BIB9","series-title":"Proc. 6th Workshop on Computer Science Logic","first-page":"43","article-title":"Optimization problems: expressibility, approximation properties and expected asymptotic growth of optimal solutions","author":"Behrendt","year":"1993"},{"key":"10.1016\/0304-3975(94)00291-P_BIB10","series-title":"Proc. 25th Ann. ACM Symp. on Theory of Computing","first-page":"294","article-title":"Efficient probabilistically checkable proofs and applications to approximation","author":"Bellare","year":"1993"},{"key":"10.1016\/0304-3975(94)00291-P_BIB11","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","article-title":"On the complexity of approximating the independent set problem","volume":"96","author":"Berman","year":"1992","journal-title":"Information and Computation"},{"key":"10.1016\/0304-3975(94)00291-P_BIB12","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","article-title":"The Steiner problem with edge lengths 1 and 2","volume":"32","author":"Bern","year":"1989","journal-title":"Inform Process. Lett."},{"key":"10.1016\/0304-3975(94)00291-P_BIB13","series-title":"Proc. 23-rd Ann. ACM Symp. on Theory of Computing","first-page":"328","article-title":"Linear approximation of shortest superstrings","author":"Blum","year":"1991"},{"key":"10.1016\/0304-3975(94)00291-P_BIB14","series-title":"Introduction to the Theory of Complexity","author":"Bovet","year":"1993"},{"key":"10.1016\/0304-3975(94)00291-P_BIB15","first-page":"1","article-title":"A structural overview of NP optimization problems","volume":"2","author":"Bruschi","year":"1991","journal-title":"Algorithms Rev."},{"key":"10.1016\/0304-3975(94)00291-P_BIB16","series-title":"Proc. 25th Ann. ACM Symp. on Theory of Computing","first-page":"305","article-title":"Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions","author":"Condon","year":"1993"},{"key":"10.1016\/0304-3975(94)00291-P_BIB17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0020-0190(05)80002-X","article-title":"A note on the approximation of the MAX CLIQUE problem","volume":"40","author":"Crescenzi","year":"1991","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(94)00291-P_BIB18","series-title":"A compendium of NP optimization problems","author":"Crescenzi","year":"1994"},{"key":"10.1016\/0304-3975(94)00291-P_BIB19","series-title":"Natural complete and intermediate problems in approximation classes","author":"Crescenzi","year":"1994"},{"key":"10.1016\/0304-3975(94)00291-P_BIB20","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0890-5401(91)90025-W","article-title":"Completeness in approximation classes","volume":"93","author":"Crescenzi","year":"1991","journal-title":"Inform. and Comput."},{"key":"10.1016\/0304-3975(94)00291-P_BIB21","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0020-0190(90)90188-4","article-title":"Relative complexity of evaluating the optimum cost and constructing the optimum for maximization problems","volume":"33","author":"Crescenzi","year":"1990","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(94)00291-P_BIB22","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1142\/S0129054193000031","article-title":"Average measure, descriptive complexity and approximation of maximization problems","volume":"4","author":"Crescenzi","year":"1993","journal-title":"Int. J. Foundations Comput. Sci."},{"key":"10.1016\/0304-3975(94)00291-P_BIB23","series-title":"On the structure of complete sets in approximation classes","author":"Crescenzi","year":"1994"},{"key":"10.1016\/0304-3975(94)00291-P_BIB24","series-title":"Proc. 14th Conference on Foundations of Software Technology and Theoretical Computer Science","first-page":"330","article-title":"On approximation scheme preserving reducibility and its applications","volume":"Vol. 880","author":"Crescenzi","year":"1994"},{"key":"10.1016\/0304-3975(94)00291-P_BIB25","series-title":"SIAM-AMS Proc.","first-page":"43","article-title":"Generalized first-order spectra and polynomial-time recognizable sets","author":"Fagin","year":"1974"},{"key":"10.1016\/0304-3975(94)00291-P_BIB26","series-title":"Proc. 32nd Ann. IEEE Symp. on Foundations of Computer Science","first-page":"2","article-title":"Approximating clique is almost NP-complete","author":"Feige","year":"1991"},{"key":"10.1016\/0304-3975(94)00291-P_BIB27","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/322077.322090","article-title":"Strong NP-completeness results: motivation, examples, and implications","volume":"25","author":"Garey","year":"1978","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(94)00291-P_BIB28","author":"Garey","year":"1979"},{"key":"10.1016\/0304-3975(94)00291-P_BIB29","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. and Systems Sci."},{"key":"10.1016\/0304-3975(94)00291-P_BIB30","series-title":"Proc. 9-th Ann. Symp. on Theoretical Aspects of Computer Science","first-page":"377","article-title":"On the approximability of the maximum common subgraph problem","author":"Kann","year":"1992"},{"key":"10.1016\/0304-3975(94)00291-P_BIB31","article-title":"On the approximability of NP-complete optimization problems","author":"Kann","year":"1992"},{"key":"10.1016\/0304-3975(94)00291-P_BIB32","series-title":"Proc. 20th Internat. Colloq. on Automata, Languages and Programming","first-page":"52","article-title":"Polynomially bounded minimization problems which are hard to approximate","author":"Kann","year":"1993"},{"key":"10.1016\/0304-3975(94)00291-P_BIB33","series-title":"Proc. 3rd Workshop on Algorithms and Data Structures","first-page":"421","article-title":"On approximating the longest path in a graph","author":"Karger","year":"1993"},{"key":"10.1016\/0304-3975(94)00291-P_BIB34","series-title":"Proc. 35th Ann. IEEE Symp. on Foundations of Computer Science","first-page":"819","article-title":"On syntactic versus computational views of approximability","author":"Khanna","year":"1994"},{"key":"10.1016\/0304-3975(94)00291-P_BIB35","doi-asserted-by":"crossref","DOI":"10.1006\/inco.1994.1100","article-title":"Logical definability of NP optimization problems","author":"Kolaitis","year":"1990"},{"key":"10.1016\/0304-3975(94)00291-P_BIB36","series-title":"Proc. 6th Structure in Complexity Theory","first-page":"353","article-title":"Approximation properties of NP minimization classes","author":"Kolaitis","year":"1991"},{"key":"10.1016\/0304-3975(94)00291-P_BIB37","series-title":"Nonlinear Programming","first-page":"415","article-title":"On the existence of fast approximation schemes","author":"Korte","year":"1981"},{"key":"10.1016\/0304-3975(94)00291-P_BIB38","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","article-title":"The complexity of optimization problems","volume":"36","author":"Krentel","year":"1988","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/0304-3975(94)00291-P_BIB39","series-title":"Proc. 25th Ann. ACM Symp. on Theory of Computing","first-page":"286","article-title":"On the hardness of approximating minimization problems","author":"Lund","year":"1993"},{"key":"10.1016\/0304-3975(94)00291-P_BIB40","doi-asserted-by":"crossref","DOI":"10.1016\/0020-0190(85)90061-4","article-title":"On different approximation criteria for subset product problems","volume":"21","author":"Marchetti-Spaccamela","year":"1985","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(94)00291-P_BIB41","article-title":"Lecture notes on approximation algorithms","author":"Motwani","year":"1992"},{"key":"10.1016\/0304-3975(94)00291-P_BIB42","article-title":"On approximation preserving reductions: complete problems and robust measures","author":"Orponen","year":"1987"},{"key":"10.1016\/0304-3975(94)00291-P_BIB43","series-title":"Proc. 22nd Ann. ACM Symp. on Theory of Computing","first-page":"446","article-title":"Quantifiers and approximation","author":"Panconesi","year":"1990"},{"key":"10.1016\/0304-3975(94)00291-P_BIB44","series-title":"Computational complexity","author":"Papadimitriou","year":"1993"},{"key":"10.1016\/0304-3975(94)00291-P_BIB45","series-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou","year":"1982"},{"key":"10.1016\/0304-3975(94)00291-P_BIB46","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","article-title":"Optimization, approximation, and complexity classes","volume":"43","author":"Papadimitriou","year":"1991","journal-title":"J. Comput. Systems Sci."},{"key":"10.1016\/0304-3975(94)00291-P_BIB47","article-title":"The traveling salesman problem with distances one and two","author":"Papadimitriou","year":"1992","journal-title":"Math. Oper. Res."},{"key":"10.1016\/0304-3975(94)00291-P_BIB48","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0304-3975(81)90081-5","article-title":"Non deterministic polynomial optimization problems and their approximations","volume":"15","author":"Paz","year":"1981","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(94)00291-P_BIB49","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1145\/321864.321873","article-title":"Approximate algorithms for the 0\/1 knapsack problem","volume":"22","author":"Sahni","year":"1975","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(94)00291-P_BIB50","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1137\/0403025","article-title":"On approximate solutions for combinatorial optimization problems","volume":"3","author":"Simon","year":"1990","journal-title":"SIAM J. Discrete Math."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759400291P?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759400291P?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,4,10]],"date-time":"2023-04-10T03:16:12Z","timestamp":1681096572000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759400291P"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,10]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,10]]}},"alternative-id":["030439759400291P"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(94)00291-p","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1995,10]]}}}