{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:15Z","timestamp":1725663615331},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540569398"},{"type":"electronic","value":"9783540478263"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56939-1_61","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T11:56:58Z","timestamp":1330257418000},"page":"52-63","source":"Crossref","is-referenced-by-count":10,"title":["Polynomially bounded minimization problems which are hard to approximate"],"prefix":"10.1007","author":[{"given":"Viggo","family":"Kann","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. of 33rd Annual IEEE Sympos. on Foundations of Computer Science, pages 14\u201323, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"5_CR2","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 and G. Schnitger. On the complexity of approximating the independent set problem. Information and Computation, 96:77\u201394, 1992.","journal-title":"Information and Computation"},{"issue":"2","key":"5_CR3","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 and A. Panconesi. Completeness in approximation classes. Information and Computation, 93(2):241\u2013262, 1991.","journal-title":"Information and Computation"},{"key":"5_CR4","volume-title":"Computers and Intractability: a guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San Fransisco, 1979."},{"key":"5_CR5","unstructured":"M. M. Halld\u00f3rsson. Approximating the minimum maximal independence number. Technical Report IS-RR-93-0001F, ISSN 0918-7553, Japan Advanced Institute of Science and Technology, JAIST, 1993."},{"key":"5_CR6","doi-asserted-by":"crossref","unstructured":"K-U. H\u00f6ffgen, H-U. Simon, and K. van Horn. Robust trainability of single neurons. Manuscript, 1992.","DOI":"10.1145\/130385.130431"},{"issue":"4","key":"5_CR7","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O. H. Ibarra","year":"1975","unstructured":"O. H. Ibarra and C. E. Kim. Fast approximation for the knapsack and sum of subset problems. Journal of the ACM, 22(4):463\u2013468, 1975.","journal-title":"Journal of the ACM"},{"key":"5_CR8","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. On approximating the minimum independent dominating set. Information Processing Letters, 37:197\u2013200, 1991.","journal-title":"Information Processing Letters"},{"key":"5_CR9","volume-title":"PhD thesis","author":"V. Kann","year":"1992","unstructured":"V. Kann. On the Approximability of NP-complete Optimization Problems. PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992."},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"V. Kann. On the approximability of the maximum common subgraph problem. In Proc. 9th Annual Symposium on Theoretical Aspects of Computer Science, pages 377\u2013388. Springer-Verlag, 1992. Lecture Notes in Computer Science 577.","DOI":"10.1007\/3-540-55210-3_198"},{"key":"5_CR11","unstructured":"P. G. Kolaitis and M. N. Thakur. Logical definability of NP optimization problems. Technical Report UCSC-CRL-90-48, Board of Studies in Computer and Information Sciences, University of California at Santa Cruz, 1990. To be published in Information and Computation."},{"key":"5_CR12","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M. W. Krentel","year":"1988","unstructured":"M. W. Krentel. The complexity of optimization problems. Journal of Computer and System Sciences, 36:490\u2013509, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"A. Panconesi and D. Ranjan. Quantifiers and approximation. In Proc. Twenty second Annual ACM symp. on Theory of Comp., pages 446\u2013456. ACM, 1990.","DOI":"10.1145\/100216.100275"},{"key":"5_CR14","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 and M. Yannakakis. Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43:425\u2013440, 1991.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"5_CR15","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/322123.322138","volume":"26","author":"N. Pippenger","year":"1979","unstructured":"N. Pippenger and M. J. Fischer. Relations among complexity measures. Journal of the ACM, 26(2):361\u2013381, 1979.","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56939-1_61.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:07:28Z","timestamp":1605647248000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56939-1_61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540569398","9783540478263"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-56939-1_61","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}