{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:55Z","timestamp":1725490255247},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540742074"},{"type":"electronic","value":"9783540742081"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74208-1_12","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T14:52:26Z","timestamp":1188226346000},"page":"164-179","source":"Crossref","is-referenced-by-count":4,"title":["Integrality Gaps of Semidefinite Programs for Vertex Cover and Relations to \u21131 Embeddability of Negative Type Metrics"],"prefix":"10.1007","author":[{"given":"Hamed","family":"Hatami","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avner","family":"Magen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Evangelos","family":"Markakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"12_CR1","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I. Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex-cover. Annals of Mathematics\u00a0162(1), 439\u2013486 (2005)","journal-title":"Annals of Mathematics"},{"key":"12_CR2","first-page":"767","volume-title":"Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (electronic)","author":"S. Khot","year":"2002","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (electronic), pp. 767\u2013775. ACM Press, New York (2002)"},{"key":"12_CR3","first-page":"379","volume-title":"Proceedings of the 18th IEEE Conference on Computational Complexity","author":"S. Khot","year":"2003","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2009\u2212\u2009\u03b5. In: Proceedings of the 18th IEEE Conference on Computational Complexity, pp. 379\u2013386. IEEE Computer Society Press, Los Alamitos (2003)"},{"issue":"6","key":"12_CR4","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach.\u00a042(6), 1115\u20131145 (1995)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"5","key":"12_CR5","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 (electronic)\u00a031(5), 1608\u20131623 (2002)","journal-title":"SIAM J. Comput (electronic)"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Karakostas, G.: A better approximation ratio for the vertex cover problem. In: Proceedings of the Thirty-Second International Colloquium on Automata, Languages and Programming (2005)","DOI":"10.1007\/11523468_84"},{"issue":"2","key":"12_CR7","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/S0895480195287541","volume":"11","author":"J. Kleinberg","year":"1998","unstructured":"Kleinberg, J., Goemans, M.X.: The Lov\u00e1sz theta function and a semidefinite programming relaxation of vertex cover. SIAM J. Discrete Math (electronic)\u00a011(2), 196\u2013204 (1998)","journal-title":"SIAM J. Discrete Math (electronic)"},{"key":"12_CR8","unstructured":"Charikar, M.: On semidefinite programming relaxations for graph coloring and vertex cover. In: SODA 2002. Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp. 616\u2013620 (2002)"},{"key":"12_CR9","first-page":"222","volume-title":"Proceedings of the 36th Annual ACM Symposium on Theory of Computing (electronic)","author":"S. Arora","year":"2004","unstructured":"Arora, S., Rao, S., Vazirani, U.: Expander flows, geometric embeddings and graph partitioning. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (electronic), pp. 222\u2013231. ACM Press, New York (2004)"},{"key":"12_CR10","first-page":"102","volume-title":"SODA 2005","author":"C. Chawla","year":"2005","unstructured":"Chawla, C., Gupta, A., R\u00e4cke, H.: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. In: SODA 2005. Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, Vancouer, BC, Canada, pp. 102\u2013111. ACM Press, New York (2005)"},{"key":"12_CR11","first-page":"553","volume-title":"STOC 2005","author":"S. Arora","year":"2005","unstructured":"Arora, S., Lee, J., Naor, A.: Euclidean distortion and the sparsest cut [extended abstract]. In: STOC 2005. Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 553\u2013562. ACM Press, New York (2005)"},{"key":"12_CR12","unstructured":"Khot, S., Vishnoi, N.: The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into \u21131. In: Proceedings of The 46-th Annual Symposium on Foundations of Computer Science (2005)"},{"key":"12_CR13","volume-title":"Proceedings of the thirty-eighth annual ACM symposium on Theory of computing","author":"N. Devanur","year":"2006","unstructured":"Devanur, N., Khot, S., Saket, R., Vishnoi, N.: Integrality gaps for sparsest cut and minimum linear arrangement problems. In: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, ACM Press, New York (2006)"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Integrality gaps of 2 \u2212 o(1) for vertex cover sdps in the lov\u00e1sz-schrijver hierarchy. In: ECCCTR: Electronic Colloquium on Computational Complexity, technical reports, TR06-152 (2006)","DOI":"10.1109\/FOCS.2007.35"},{"key":"12_CR15","first-page":"573","volume-title":"STOC 2005","author":"A. Agarwal","year":"2005","unstructured":"Agarwal, A., Charikar, M., Makarychev, K., Makarychev, Y.: $O(\\sqrt{\\log n})$ approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. In: STOC 2005. Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 573\u2013581. ACM Press, New York (2005)"},{"key":"12_CR16","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of cuts and metrics","author":"M. Deza","year":"1997","unstructured":"Deza, M., Laurent, M.: Geometry of cuts and metrics, p. 587. Springer-Verlag, Berlin (1997)"},{"key":"12_CR17","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms","author":"R. Krauthgamer","year":"2006","unstructured":"Krauthgamer, R., Rabani, Y.: Improved lower bounds for embeddings into l 1. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, ACM Press, New York (2006)"},{"issue":"1","key":"12_CR18","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1090\/S0002-9947-1987-0871675-6","volume":"300","author":"P. Frankl","year":"1987","unstructured":"Frankl, P., R\u00f6dl, V.: Forbidden intersections. Trans. Amer. Math. Soc.\u00a0300(1), 259\u2013286 (1987)","journal-title":"Trans. Amer. Math. Soc."},{"issue":"2","key":"12_CR19","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0801013","volume":"1","author":"L. Lov\u00e1sz","year":"1991","unstructured":"Lov\u00e1sz, L., Schrijver, A.: Cones of matrices and set-functions and 0-1 optimization. SIAM Journal on Optimization\u00a01(2), 166\u2013190 (1991)","journal-title":"SIAM Journal on Optimization"},{"key":"12_CR20","volume-title":"STOC 2005","author":"S. Arora","year":"2005","unstructured":"Arora, S., Alekhnovich, M., Tourlakis, I.: Towards strong nonapproximability results in the lov\u00e1sz-schrijver hierarchy. In: STOC 2005. Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, ACM Press, New York (2005)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74208-1_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T16:29:47Z","timestamp":1556814587000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74208-1_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540742074","9783540742081"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74208-1_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}