Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k -Coverage, Unique Set Cover and Related Problems (via t -Wise Agreement Testing Theorem)
Pasin Manurangsi · Society for Industrial and Applied Mathematics eBooks · 2019
We show, assuming the (randomized) Gap Exponential Time Hypothesis (Gap-ETH), that the following tasks cannot be done in T(k) · No(k)-time for any function T where N denote the input size: -approximation for Max k-Coverage for any constant ɛ > 0, -approximation for k-Median (in general metrics) for any constant ɛ > 0. -approximation for k-Mean (in general metrics) for any constant ɛ > 0. Any constant factor approximation for k-Unique Set Cover, k-Nearest Codeword Problem and k-Closest Vector Problem. (1 + δ)-approximation for k-Minimum Distance Problem and k-Shortest Vector Problem for some δ > 0. Since all problems considered here can be trivially solved in NO(k) time, our running time lower bounds are tight up to a constant factor in the exponent. In terms of approximation ratios, Max k-Coverage is well-known to admit polynomial-time -approximation algorithms, and, recently, it was shown that k-Median and k-Median are approximable to within factors of and respectively in FPT time [20]; hence, our inapproximability ratios are also tight for these three problems. For the remaining problems, no non-trivial FPT approximation algorithms are known. The starting point of all our hardness results is the Label Cover problem (with projection constraints). We show that Label Cover cannot be approximated to within any constant factor in T(k) · No(k) time, where N and k denote the size of the input and the number of nodes on the side with the larger alphabet respectively. With this hardness, the above results follow immediately from known reductions. The hardness of Label Cover is in turn shown via a t-wise agreement testing theorem of the following form: given local boolean functions f1, …,fk on domains S1, …, Sk ⊆ [n], if random t functions “weakly agree” with sufficiently large probability, then we can find a global boolean function g: [n] → {0, 1} that “mostly agrees” with “many” of the local functions. We prove such a statement in the regime where S1, …, Sk are “random-looking” sets of size Θ(n/k).