{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T00:14:38Z","timestamp":1758845678635},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540632481"},{"type":"electronic","value":"9783540692478"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63248-4_10","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:22:15Z","timestamp":1330298535000},"page":"111-118","source":"Crossref","is-referenced-by-count":44,"title":["Approximation on the web: A compendium of NP optimization problems"],"prefix":"10.1007","author":[{"given":"P.","family":"Crescenzi","sequence":"first","affiliation":[]},{"given":"V.","family":"Kann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"10_CR1","unstructured":"Arora, S., and Lund, C. (1997), Hardness of approximations, chapter 10 of [11]. PWS, 1997."},{"key":"10_CR2","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti Spaccamela, A., and Protasi, M. (1997), Approximate solution of NP-hard optimization problems. To appear (a preliminary version of some chapters is available on request to one of the authors)."},{"key":"10_CR3","unstructured":"Bovet, D., and Crescenzi, P. (1993), Introduction to the Theory of Complexity. Prentice Hall."},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Bertsimas, D., Teo, C-P., and Vohra, R. (1996), \u201cOn dependent randomized rounding algorithms\u201d, Proc. 5th Int. Conf. on Integer Prog. and Combinatorial Optimization, Lecture Notes in Comput. Sci. 1084, Springer-Verlag, 330\u2013344.","DOI":"10.1007\/3-540-61310-2_25"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Crescenzi, P., Kann, V., Silvestri, R., and Trevisan, L. (1995), \u201cStructure in approximation classes\u201d, Proc. 1st Ann. Int. Conf. on Computing and Combinatorics, Lecture Notes in Comput. Sci. 959, Springer-Verlag, 539\u2013548.","DOI":"10.1007\/BFb0030875"},{"key":"10_CR6","unstructured":"Feige, U. (1996), \u201cA threshold of In n for approximating set cover\u201d, Proc. 28th Ann. ACM Symp. on Theory of Comp., ACM, 314\u2013318."},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Feige, U., and Goemans, M. X. (1995), \u201cApproximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT\u201d, Proc. 3rd Israel Symp. on Theory of Computing and Systems, IEEE Computer Society, 182\u2013189.","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"10_CR8","volume-title":"Computers and Intractability: a guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., and Johnson, D. S. (1979), Computers and Intractability: a guide to the theory of NP-completeness, W. H. Freeman and Company, San Francisco."},{"key":"10_CR9","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M. X. Goemans","year":"1995","unstructured":"Goemans, M. X., and Williamson, D. P. (1995b), \u201cImproved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming\u201d, J. ACM\n42, 1115\u20131145.","journal-title":"J. ACM"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J. (1997), \u201cSome optimal inapproximability results\u201d, Proc. 29th Ann. ACM Symp. on Theory of Comp., ACM, 1\u201310.","DOI":"10.1145\/258533.258536"},{"volume-title":"Approximation algorithms for NP-hard problems","year":"1997","key":"10_CR11","unstructured":"Hochbaum, D. S. ed. (1997), Approximation algorithms for NP-hard problems, PWS Publishing Company, Boston."},{"key":"10_CR12","doi-asserted-by":"crossref","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. Comp.\n10, 718\u2013720.","journal-title":"SIAM J. Comp."},{"key":"10_CR13","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":"10_CR14","volume-title":"PhD thesis, Department of Numerical Analysis and Computing Science","author":"V. Kann","year":"1992","unstructured":"Kann, V. (1992b), On the Approximability of NP-complete Optimization Problems, PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm."},{"key":"10_CR15","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1137\/0403035","volume":"3","author":"T. Nishizeki","year":"1990","unstructured":"Nishizeki, T., and Kashiwagi, K. (1990), \u201cOn the 1.1 edge-coloring of multigraphs\u201d, SIAM J. Disc. Math.\n3, 391\u2013410.","journal-title":"SIAM J. Disc. Math."},{"key":"10_CR16","unstructured":"Papadimitriou, C.H. (1994), Computational Complexity. Addison-Wesley."},{"key":"10_CR17","unstructured":"Papadimitriou, C.H., and Steiglitz, K. (1982), Combinatorial optimization: algorithms and complexity, Prentice Hall."},{"key":"10_CR18","doi-asserted-by":"crossref","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":"10_CR19","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF01202286","volume":"4","author":"E. Petrank","year":"1994","unstructured":"Petrank, E. (1994), \u201cThe hardness of approximation: gap location\u201d, Computational Complexity\n4, 133\u2013157.","journal-title":"Computational Complexity"},{"key":"10_CR20","first-page":"23","volume":"3","author":"V. G. Vizing","year":"1964","unstructured":"Vizing, V. G. (1964), \u201cOn an estimate of the chromatic class of a p-graph\u201d, Diskret. Analiz.\n3, 23\u201330.","journal-title":"Diskret. Analiz."}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63248-4_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:43:19Z","timestamp":1619574199000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63248-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540632481","9783540692478"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-63248-4_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}