2013 IEEE 54th Annual Symposium on Foundations of Computer Science (2007)
Providence, Rhode Island
Oct. 21, 2007 to Oct. 23, 2007
ISSN: 0272-5428
ISBN: 0-7695-3010-9
pp: 702-712
ABSTRACT
<p>Linear and semidefinite programming are highly successful approaches for obtaining good approximations for NP-hard optimization problems. For example, breakthrough approximation algorithms for MAX CUT and SPARSEST CUT use semidefinite programming.</p><p> Perhaps the most prominent NP-hard problem whose exact approximation factor is still unresolved is VERTEX COVER. PCP-based techniques of Dinur and Safra [7] show that it is not possible to achieve a factor better than 1.36; on the other hand no known algorithm does better than the factor of 2 achieved by the simple greedy algorithm. Furthermore, there is a widespread belief that SDP techniques are the most promising methods available for improving upon this factor of 2.</p><p> Following a line of study initiated by Arora et al. [3], our aim is to show that a large family of LP and SDP based algorithms fail to produce an approximation for VERTEX COVER better than 2. Lovész and Schrijver [21] introduced the systems LS and LS_ + for systematically tightening LP and SDP relaxations, respectively, over many rounds. These systems naturally capture large classes of LP and SDP relaxations; indeed, LS_ + captures the celebrated SDP-based algorithms for MAX CUT and SPARSEST CUT mentioned above.</p><p> We rule out polynomial-time 2 - \Omega (1) approximations for VERTEX COVER using LS_ +. In particular, we prove an integrality gap of 2-o(1) for VERTEX COVER SDPs obtained by tightening the standard LP relaxation with \Omega (\sqrt {\log n/\log \log n} ) rounds of LS_ +. While tight integrality gaps were known for VERTEX COVER in the weaker LS system [23], previous results did not rule out a 2 - \Omega (1) approximation after even two rounds of LS_ +.</p>
INDEX TERMS
null
CITATION
Toniann Pitassi, Avner Magen, Iannis Tourlakis, Konstantinos Georgiou, "Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy", 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, vol. 00, no. , pp. 702-712, 2007, doi:10.1109/FOCS.2007.35
CITATIONS
SHARE
259 ms
(Ver 3.3 (11022016))
{"extraction_info": {"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.8770038485527039, "perplexity": 1421.4216439798236}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2017-39/segments/1505818689775.56/warc/CC-MAIN-20170923175524-20170923195524-00591.warc.gz"}