{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T05:04:57Z","timestamp":1740287097347,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642143540"},{"type":"electronic","value":"9783642143557"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14355-7_17","type":"book-chapter","created":{"date-parts":[[2010,6,23]],"date-time":"2010-06-23T13:34:40Z","timestamp":1277300080000},"page":"161-169","source":"Crossref","is-referenced-by-count":0,"title":["On the Approximability of the Vertex Cover and Related Problems"],"prefix":"10.1007","author":[{"given":"Qiaoming","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abraham P.","family":"Punnen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Bollob\u00e0s, B., Lov\u00e0sz, L.: Proving integrality gaps without knowing the linear program. In: Proc. IEEE FOCS, pp. 313\u2013322 (2002)","DOI":"10.1109\/SFCS.2002.1181954"},{"key":"17_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-540-72845-0_22","volume-title":"Experimental Algorithms","author":"E. Asgeirsson","year":"2007","unstructured":"Asgeirsson, E., Stein, C.: Vertex cover approximations on random graphs. In: Demetrescu, C. (ed.) WEA 2007. LNCS, vol.\u00a04525, pp. 285\u2013296. Springer, Heidelberg (2007)"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Asgeirsson, E., Stein, C.: Vertex cover approximations: Experiments and observations. In: WEA, pp. 545\u2013557 (2005)","DOI":"10.1007\/11427186_47"},{"key":"17_CR4","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics\u00a025, 27\u201345 (1985)","journal-title":"Annals of Discrete Mathematics"},{"key":"17_CR5","unstructured":"Charikar, M.: On semidefinite programming relaxations for graph coloring and vertex cover. In: Proc. 13th SODA, pp. 616\u2013620 (2002)"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Dinur, I., Safra, S.: The importance of being biased. In: Proc. 34th ACM Symposium on Theory of Computing, pp. 33\u201342 (2002)","DOI":"10.1145\/509907.509915"},{"key":"17_CR7","doi-asserted-by":"publisher","first-page":"1608","DOI":"10.1137\/S0097539700381097","volume":"31","author":"E. Halperin","year":"2002","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM J. Comput.\u00a031, 1608\u20131623 (2002)","journal-title":"SIAM J. Comput."},{"key":"17_CR8","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.orl.2009.01.010","volume":"37","author":"Q. Han","year":"2009","unstructured":"Han, Q., Punnen, A.P., Ye, Y.: A polynomial time $\\frac 3 2$ -approximation algorithm for the vertex cover problem on a class of graphs. Operations Research Letters\u00a037, 181\u2013186 (2009)","journal-title":"Operations Research Letters"},{"key":"17_CR9","unstructured":"Harb, B.: The unique games conjecture and some of its implications on inapproximability (May 2005) (manuscript)"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. JACM\u00a048, 798\u2013859 (2001)","journal-title":"JACM"},{"key":"17_CR11","unstructured":"Hochbaum, D.S.: Approximating covering and packing problems: set cover, independent set, and related problems. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems, pp. 94\u2013143. PWS Publishing Company (1997)"},{"key":"17_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1043","DOI":"10.1007\/11523468_84","volume-title":"Automata, Languages and Programming","author":"G. Karakostas","year":"2005","unstructured":"Karakostas, G.: A better approximation ratio for the vertex cover problem. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1043\u20131050. Springer, Heidelberg (2005)"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-Prover 1-Round games. In: Proceedings of 34th ACM Symposium on Theory of Computing (STOC), pp. 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2 \u2212 \u03b5. In: Complexity (2003)","DOI":"10.1109\/CCC.2003.1214437"},{"key":"17_CR15","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/S0895480195287541","volume":"11","author":"J. Kleinberg","year":"1998","unstructured":"Kleinberg, J., Goemans, M.: The Lov\u00e1sz theta function and a semidefinite programming relaxation of vertex cover. SIAM J. Discrete Math.\u00a011, 196\u2013204 (1998)","journal-title":"SIAM J. Discrete Math."},{"key":"17_CR16","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/BF00290149","volume":"22","author":"B. Monien","year":"1985","unstructured":"Monien, B., Speckenmeyer, E.: Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Informatica\u00a022, 115\u2013123 (1985)","journal-title":"Acta Informatica"},{"key":"17_CR17","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/BF01580222","volume":"6","author":"G.L. Nemhauser","year":"1974","unstructured":"Nemhauser, G.L., Trotter Jr., L.E.: Properties of vertex packing and independence system polyhedra. Mathematical Programming\u00a06, 48\u201361 (1974)","journal-title":"Mathematical Programming"},{"key":"17_CR18","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter Jr., L.E.: Vertex packings: Structural properties and algorithms. Mathematical Programming\u00a08, 232\u2013248 (1975)","journal-title":"Mathematical Programming"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14355-7_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T05:37:44Z","timestamp":1740202664000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14355-7_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642143540","9783642143557"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14355-7_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}