{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:30:09Z","timestamp":1725514209566},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540688860"},{"type":"electronic","value":"9783540688914"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-68891-4_10","type":"book-chapter","created":{"date-parts":[[2008,5,23]],"date-time":"2008-05-23T09:31:37Z","timestamp":1211535097000},"page":"140-153","source":"Crossref","is-referenced-by-count":1,"title":["Vertex Cover Resists SDPs Tightened by Local Hypermetric Inequalities"],"prefix":"10.1007","author":[{"given":"Konstantinos","family":"Georgiou","sequence":"first","affiliation":[]},{"given":"Avner","family":"Magen","sequence":"additional","affiliation":[]},{"given":"Iannis","family":"Tourlakis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/1109557.1109563","volume-title":"SODA","author":"S. Arora","year":"2006","unstructured":"Arora, S., Lov\u00e1sz, L., Newman, I., Rabani, Y., Rabinovich, Y., Vempala, S.: Local versus global properties of metric spaces. In: SODA, pp. 41\u201350. ACM Press, New York (2006)"},{"key":"10_CR2","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, New York (2004)"},{"issue":"3","key":"10_CR3","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10107-003-0423-5","volume":"97","author":"D. Avis","year":"2003","unstructured":"Avis, D., Umemoto, J.: Stronger linear programming relaxations of max-cut. Mathematical Programming\u00a097(3), 451\u2013469 (2003)","journal-title":"Mathematical Programming"},{"key":"#cr-split#-10_CR4.1","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, pp. 616???620 (2002);"},{"key":"#cr-split#-10_CR4.2","unstructured":"Society for Industrial and Applied Mathematics"},{"key":"10_CR5","first-page":"713","volume-title":"Proceedings of the Forty-Eighth Annual IEEE Symposium on Foundations of Computer Science","author":"M. Charikar","year":"2007","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Local global tradeoffs in metric embeddings. In: Proceedings of the Forty-Eighth Annual IEEE Symposium on Foundations of Computer Science, pp. 713\u2013723. IEEE, Los Alamitos (2007)"},{"key":"10_CR6","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1145\/1132516.1132594","volume-title":"STOC 2006. Proceedings of the 38th Annual ACM Symposium on Theory of Computing","author":"N.R. Devanur","year":"2006","unstructured":"Devanur, N.R., Khot, S.A., Saket, R., Vishnoi, N.K.: Integrality gaps for sparsest cut and minimum linear arrangement problems. In: STOC 2006. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 537\u2013546. ACM, New York (2006)"},{"key":"10_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-04295-9","volume-title":"Geometry of cuts and metrics. Algorithms and Combinatorics","author":"M. Deza","year":"1997","unstructured":"Deza, M., Laurent, M.: Geometry of cuts and metrics. Algorithms and Combinatorics, vol.\u00a015. Springer, Berlin, Heidelberg, New York, Barcelona, Budapest, Hong Kong, London, Mailand, Paris, Santa Clara, Singapur, Tokyo (1997)"},{"issue":"1","key":"10_CR8","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"},{"issue":"1","key":"10_CR9","doi-asserted-by":"publisher","first-page":"259","DOI":"10.2307\/2000598","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."},{"key":"10_CR10","first-page":"702","volume-title":"Proceedings of the Forty-Eighth Annual IEEE Symposium on Foundations of Computer Science","author":"K. Georgiou","year":"2007","unstructured":"Georgiou, K., Magen, A., Pitassi, T., Tourlakis, I.: Integrality gaps of 2\u2009\u2212\u2009o(1) for vertex cover SDPs in the Lov\u00e1sz-Schrijver hierarchy. In: Proceedings of the Forty-Eighth Annual IEEE Symposium on Foundations of Computer Science, pp. 702\u2013712. IEEE, Los Alamitos (2007)"},{"issue":"6","key":"10_CR11","doi-asserted-by":"crossref","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":"10_CR12","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":"10_CR13","doi-asserted-by":"crossref","unstructured":"Hatami, H., Magen, A., Markakis, E.: Integrality gaps of semidefinite programs for vertex cover and relations to 1 embeddability of negative type metrics. In: APPROX-RANDOM, pp. 164\u2013179 (2007)","DOI":"10.1007\/978-3-540-74208-1_12"},{"key":"10_CR14","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":"10_CR15","doi-asserted-by":"publisher","first-page":"767","DOI":"10.1145\/509907.510017","volume-title":"Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing","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, pp. 767\u2013775. ACM, New York (2002)"},{"key":"10_CR16","doi-asserted-by":"crossref","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 (2003)","DOI":"10.1109\/CCC.2003.1214437"},{"issue":"2","key":"10_CR17","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.\u00a011(2), 196\u2013204 (1998)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"10_CR18","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"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-68891-4_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T00:17:44Z","timestamp":1620001064000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-68891-4_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540688860","9783540688914"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-68891-4_10","relation":{},"subject":[]}}