Bansal Nikhil, Chalermsook Parinya, Laekhanukit Bundit, Nanongkai Danupon, Nederlof Jesper
1Eindhoven University of Technology, Eindhoven, The Netherlands.
2Aalto University, Helsinki, Finland.
Algorithmica. 2019;81(10):3993-4009. doi: 10.1007/s00453-018-0512-8. Epub 2018 Sep 5.
In this paper, we develop new tools and connections for . In this setting, we are given a problem instance and an integer , and the goal is to design an approximation algorithm with the fastest possible running time. We give randomized algorithms that establish an approximation ratio of for maximum independent set in time, for chromatic number in time, for minimum vertex cover in time, and for minimum -hypergraph vertex cover in time. (Throughout, and omit and factors polynomial in the input size, respectively.) The best known time bounds for all problems were (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 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 bounds are not tight for all these problems. The key to these results is a 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 . 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).
在本文中，我们为……开发了新工具和联系。在这种情况下，我们给定一个问题实例和一个整数，目标是设计一个运行时间尽可能快的近似算法。我们给出了随机算法，该算法对于最大独立集在时间内建立近似比率为，对于色数在时间内，对于最小顶点覆盖在时间内，对于最小超图顶点覆盖在时间内。（始终分别省略输入大小的和多项式因子。）所有问题的最知名时间界限是（布尔乔亚等人，《离散应用数学》159(17):1954 - 1970，2011；西甘等人，《难题的指数时间近似》，2008）。对于最大独立集和色数，这些界限由下界补充（在指数时间假设（ETH）下）（查勒姆苏克等人，《计算机科学基础》，FOCS，第370 - 379页，2013；莱卡努基特，《亚指数时间内组合问题的不可近似性》。博士论文，2014）。我们的结果表明，对于所有这些问题，看似自然的界限并不紧密。这些结果的关键是一个将问题简化为有界度变体的过程，允许使用有界度图的近似算法。为了获得前两个结果，我们引入了一个新的……。最后，我们展示了PCP参数与指数时间近似算法之间的联系。这种联系与我们的独立集算法一起反驳了过度减小陈的PCP大小的可能性（陈，《美国计算机协会杂志》63(3):27:1 - 27:32，2016）。它还意味着对我们结果的（显著）改进将反驳差距 - ETH猜想（迪努尔，《电子计算复杂性电子公告》（ECCC）23:128，2016；马努朗西和拉格万德拉，《生日重复定理与近似密集CSP的复杂性》，2016）。
