{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T14:13:36Z","timestamp":1778249616340,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540602163","type":"print"},{"value":"9783540447337","type":"electronic"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0030875","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T03:51:40Z","timestamp":1133409100000},"page":"539-548","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Structure in approximation classes"],"prefix":"10.1007","author":[{"given":"P.","family":"Crescenzi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V.","family":"Kann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Silvestri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L.","family":"Trevisan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,20]]},"reference":[{"key":"62_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. (1992), \u201cProof verification and hardness of approximation problems\u201d, Proc. of 33rd Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"62_CR2","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0890-5401(92)90056-L","volume":"96","author":"P. Berman","year":"1992","unstructured":"Berman, P., and Schnitger, G. (1992), \u201cOn the complexity of approximating the independent set problem\u201d, Inform. and Comput.\n96, 77\u201394.","journal-title":"Inform. and Comput."},{"key":"62_CR3","unstructured":"Bovet, D.P., and Crescenzi, P. (1993), Introduction to the theory of complexity. Prentice Hall."},{"key":"62_CR4","doi-asserted-by":"crossref","unstructured":"Chang, R. (1994), \u201cOn the query complexity of clique size and maximum satisfiability\u201d, Proc. 9th Ann. Structure in Complexity Theory Conf., IEEE Computer Society, 31\u201342 (an extended version is available as Technical Report TR-CS-95-01, Department of Computer Science, University of Maryland Baltimore County, April 1995).","DOI":"10.1109\/SCT.1994.315820"},{"key":"62_CR5","first-page":"166","volume":"54","author":"R. Chang","year":"1994","unstructured":"Chang, R. (1994), \u201cA machine model for NP-approximation problems and the revenge of the Boolean hierarchy\u201d, EATCS Bulletin\n54, 166\u2013182.","journal-title":"EATCS Bulletin"},{"key":"62_CR6","unstructured":"Chang, R., Gasarch, W.I., and Lund, C. (1994), \u201cOn bounded queries and approximation\u201d, Technical Report TR CS-94-05, Department of Computer Science, University of Maryland Baltimore County."},{"key":"62_CR7","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0890-5401(91)90025-W","volume":"93","author":"P. Crescenzi","year":"1991","unstructured":"Crescenzi, P., and Panconesi, A. (1991), \u201cCompleteness in approximation classes\u201d, Inform. and Comput.\n93, 241\u2013262.","journal-title":"Inform. and Comput."},{"key":"62_CR8","doi-asserted-by":"crossref","unstructured":"Crescenzi, P., and Trevisan, L. (1994), \u201cOn approximation scheme preserving reducibility and its applications\u201d, Proc. 14th FSTTCS, Lecture Notes in Comput. Sci. 880, Springer-Verlag, 330\u2013341.","DOI":"10.1007\/3-540-58715-2_135"},{"key":"62_CR9","unstructured":"F\u00fcrer, M., and Raghavachari, B. (1992), \u201cApproximating the minimum degree spanning tree to within one from the optimal degree\u201d, Proc. Third Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, 317\u2013324."},{"key":"62_CR10","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I. Holyer","year":"1981","unstructured":"Holyer, I. (1981), \u201cThe NP-completeness of edge-coloring\u201d, SIAM J. Computing\n10, 718\u2013720.","journal-title":"SIAM J. Computing"},{"key":"62_CR11","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnson","year":"1974","unstructured":"Johnson, D.S. (1974), \u201cApproximation algorithms for combinatorial problems\u201d, J. Comput. System Sci.\n9, 256\u2013278.","journal-title":"J. Comput. System Sci."},{"key":"62_CR12","volume-title":"PhD thesis","author":"V. Kann","year":"1992","unstructured":"Kann, V. (1992), On the approximability of NP-complete optimization problems, PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm."},{"key":"62_CR13","first-page":"317","volume":"1","author":"V. Kann","year":"1994","unstructured":"Kann, V. (1994), \u201cPolynomially bounded minimization problems that are hard to approximate\u201d, Nordic J. Computing\n1, 317\u2013331.","journal-title":"Nordic J. Computing"},{"key":"62_CR14","doi-asserted-by":"crossref","unstructured":"Kann, V. (1995), \u201cStrong lower bounds of the approximability of some NPO PB-complete maximization problems\u201d, Proc. MFCS, to appear.","DOI":"10.1007\/3-540-60246-1_129"},{"key":"62_CR15","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., and Karp, R. M. (1982), \u201cAn efficient approximation scheme for the one-dimensional bin packing problem\u201d, Proc. of 23rd Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 312\u2013320.","DOI":"10.1109\/SFCS.1982.61"},{"key":"62_CR16","doi-asserted-by":"crossref","unstructured":"Khanna, S., Motwani, R., Sudan, M., and Vazirani, U. (1994), \u201cOn syntactic versus computational views of approximability\u201d, Proc. of 35th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, 819\u2013830.","DOI":"10.1109\/SFCS.1994.365712"},{"key":"62_CR17","doi-asserted-by":"crossref","unstructured":"Kolaitis, P. G., and Thakur, M. N. (1991), \u201cApproximation properties of NP minimization classes\u201d, Proc. Sixth Ann. Structure in Complexity Theory Conf., IEEE Computer Society, 353\u2013366.","DOI":"10.1109\/SCT.1991.160280"},{"key":"62_CR18","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M.W. Krentel","year":"1988","unstructured":"Krentel, M.W. (1988), \u201cThe complexity of optimization problems\u201d, J. Comput. System Sci.\n36, 490\u2013509.","journal-title":"J. Comput. System Sci."},{"key":"62_CR19","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E. (1975), \u201cOn the structure of polynomial-time reducibility\u201d, J. ACM\n22, 155\u2013171.","journal-title":"J. ACM"},{"key":"62_CR20","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"Lund, C., and Yannakakis, M. (1994), \u201cOn the hardness of approximating minimization problems\u201d, J. ACM\n41, 960\u2013981.","journal-title":"J. ACM"},{"key":"62_CR21","doi-asserted-by":"crossref","unstructured":"Lund, C., and Yannakakis, M. (1993), \u201cThe approximation of maximum subgraph problems\u201d, Proc. of 20th International Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 700, Springer-Verlag, 40\u201351.","DOI":"10.1007\/3-540-56939-1_60"},{"key":"62_CR22","unstructured":"Motwani, R. (1992), \u201cLecture notes on approximation algorithms\u201d, Technical Report STAN-CS-92-1435, Department of Computer Science, Stanford University, 1992."},{"key":"62_CR23","unstructured":"Orponen, P., and Mannila, H. (1987), \u201cOn approximation preserving reductions: Complete problems and robust measures\u201d, Technical Report C-1987-28, Department of Computer Science, University of Helsinki."},{"key":"62_CR24","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0304-3975(93)90259-V","volume":"107","author":"A. Panconesi","year":"1993","unstructured":"Panconesi, A., and Ranjan, D. (1993), \u201cQuantifiers and approximation\u201d, Theoretical Computer Science\n107, 145\u2013163.","journal-title":"Theoretical Computer Science"},{"key":"62_CR25","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C. H., and Yannakakis, M. (1991), \u201cOptimization, approximation, and complexity classes\u201d, J. Comput. System Sci.\n43, 425\u2013440.","journal-title":"J. Comput. System Sci."},{"key":"62_CR26","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U. (1986), \u201cGraph isomorphism is in the low hierarchy\u201d, Proc. 4th Ann. Symp. on Theoretical Aspects of Comput. Sci., Lecture Notes in Comput. Sci. 247, Springer-Verlag, 114\u2013124.","DOI":"10.1007\/BFb0039599"},{"key":"62_CR27","doi-asserted-by":"crossref","unstructured":"Wagner, K. (1988), \u201cBounded query computations\u201d, Proc. 3rd Ann. Structure in Complexity Theory Conf., IEEE Computer Society, 260\u2013277.","DOI":"10.1109\/SCT.1988.5286"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0030875","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T13:30:58Z","timestamp":1778247058000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0030875"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602163","9783540447337"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/bfb0030875","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"20 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}