Manurangsi, Pasin ;
Trevisan, Luca
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
Abstract
In this work, we study the tradeoff between the running time of approximation algorithms and their approximation guarantees. By leveraging a structure of the "hard" instances of the AroraRaoVazirani lemma [Sanjeev Arora et al., 2009; James R. Lee, 2005], we show that the SumofSquares hierarchy can be adapted to provide "fast", but still exponential time, approximation algorithms for several problems in the regime where they are believed to be NPhard. Specifically, our framework yields the following algorithms; here n denote the number of vertices of the graph and r can be any positive real number greater than 1 (possibly depending on n).
 A (2  1/(O(r)))approximation algorithm for Vertex Cover that runs in exp (n/(2^{r^2)})n^{O(1)} time.
 An O(r)approximation algorithms for Uniform Sparsest Cut and Balanced Separator that runs in exp (n/(2^{r^2)})n^{O(1)} time.
Our algorithm for Vertex Cover improves upon Bansal et al.'s algorithm [Nikhil Bansal et al., 2017] which achieves (2  1/(O(r)))approximation in time exp (n/(r^r))n^{O(1)}. For Uniform Sparsest Cut and Balanced Separator, our algorithms improve upon O(r)approximation exp (n/(2^r))n^{O(1)}time algorithms that follow from a work of Charikar et al. [Moses Charikar et al., 2010].
BibTeX  Entry
@InProceedings{manurangsi_et_al:LIPIcs:2018:9424,
author = {Pasin Manurangsi and Luca Trevisan},
title = {{Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {20:120:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770859},
ISSN = {18688969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9424},
URN = {urn:nbn:de:0030drops94241},
doi = {10.4230/LIPIcs.APPROXRANDOM.2018.20},
annote = {Keywords: Approximation algorithms, Exponentialtime algorithms, Vertex Cover, Sparsest Cut, Balanced Separator}
}
13.08.2018
Keywords: 

Approximation algorithms, Exponentialtime algorithms, Vertex Cover, Sparsest Cut, Balanced Separator 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Issue date: 

2018 
Date of publication: 

13.08.2018 