2018/07/25 by Manurangsi, Pasin, Trevisan, Luca
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1807.09898
In this work, we study the trade-off between the running time of approximation algorithms and their approximation guarantees. By leveraging a structure of the `hard' instances of the Arora-Rao-Vazirani lemma [JACM'09], we show that the Sum-of-Squares 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 NP-hard. 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). (i) A (2 - (1)/(O(r)))-approximation algorithm for Vertex Cover that runs in exp(\fracn2r2)nO(1) time. (ii) An O(r)-approximation algorithms for Uniform Sparsest Cut, Balanced Separator, Minimum UnCut and Minimum 2CNF Deletion that runs in exp(\fracn2r2)nO(1) time. Our algorithm for Vertex Cover improves upon Bansal et al.'s algorithm [arXiv:1708.03515] which achieves (2 - (1)/(O(r)))-approximation in time exp((n)/(rr))nO(1). For the remaining problems, our algorithms improve upon O(r)-approximation exp((n)/(2r))nO(1)-time algorithms that follow from a work of Charikar et al. [SIAM J. Comput.'10].