aalto1 untyped-item.component.html
New Tools and Connections for Exponential-Time Approximation
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
Algorithmica
Abstract
In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and an integer r> 1 , and the goal is to design an approximation algorithm with the fastest possible running time. We give randomized algorithms that establish an approximation ratio of1.r for maximum independent set in O∗(exp (O~ (n/ rlog 2r+ rlog 2r))) time,2.r for chromatic number in O∗(exp (O~ (n/ rlog r+ rlog 2r))) time,3.(2 - 1 / r) for minimum vertex cover in O∗(exp (n/ rΩ ( r ))) time, and4.(k- 1 / r) for minimum k-hypergraph vertex cover in O∗(exp (n/ (kr) Ω ( k r ))) time. (Throughout, O~ and O∗ omit polyloglog (r) and factors polynomial in the input size, respectively.) The best known time bounds for all problems were O∗(2 n / r) (Bourgeois et al. in Discret Appl Math 159(17):1954–1970, 2011; Cygan et al. in Exponential-time approximation of hard problems, 2008). For maximum independent set and chromatic number, these bounds were complemented by exp (n1 - o ( 1 )/ r1 + o ( 1 )) lower bounds (under the Exponential Time Hypothesis (ETH)) (Chalermsook et al. in Foundations of computer science, FOCS, pp. 370–379, 2013; Laekhanukit in Inapproximability of combinatorial problems in subexponential-time. Ph.D. thesis, 2014). Our results show that the naturally-looking O∗(2 n / r) bounds are not tight for all these problems. The key to these results is a sparsification procedure that reduces a problem to a bounded-degree variant, allowing the use of approximation algorithms for bounded-degree graphs. To obtain the first two results, we introduce a new randomized branching rule. Finally, we show a connection between PCP parameters and exponential-time approximation algorithms. This connection together with our independent set algorithm refute the possibility to overly reduce the size of Chan’s PCP (Chan in J. ACM 63(3):27:1–27:32, 2016). It also implies that a (significant) improvement over our result will refute the gap-ETH conjecture (Dinur in Electron Colloq Comput Complex (ECCC) 23:128, 2016; Manurangsi and Raghavendra in A birthday repetition theorem and complexity of approximating dense CSPs, 2016).
Description
| openaire: EC/H2020/759557/EU//ALGOCom
Other note
Citation
Bansal, N, Chalermsook, P, Laekhanukit, B, Nanongkai, D & Nederlof, J 2018, 'New Tools and Connections for Exponential-Time Approximation', Algorithmica. https://doi.org/10.1007/s00453-018-0512-8