On the Fine-Grained Complexity of Approximating Max k-Coverage
Author: 
Haoqi WangAuthors Info & Claims
Pages 79 - 93
Abstract
The max k-coverage problem asks us to select k subsets from a collection S of subsets of a universe U, such that the union of these k subsets covers as many elements of U as possible. We prove that for every and , there exists an algorithm which, given a max k-coverage instance with input size N, finds k sets that cover at least elements for max k-coverage in -time, where opt is the number of elements covered by the optimal solution. On the other hand, we show that, assuming the Gap Exponential Time Hypothesis, while is a constant, the fastest -approximation algorithm for max k-coverage running in time satisfies . While non constant is a small function of k, the fastest -approximation for max k-coverage running in time satisfies .
References
[1]
Arora S, Lund C, Motwani R, Sudan M, and Szegedy M Proof verification and the hardness of approximation problems J. ACM (JACM) 1998 45 3 501-555
[2]
Bringmann, K., Cassis, A., Fischer, N., Künnemann, M.: A structural investigation of the approximability of polynomial-time problems. In: Bojanczyk, M., Merelli, E., Woodruff, D.P. (eds.) 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France. LIPIcs, vol. 229, pp. 30:1–30:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022).
[3]
Dikstein, Y., Dinur, I.: Agreement testing theorems on layered set systems. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1495–1524. IEEE (2019)
[4]
Eisenbrand F and Grandoni F On the complexity of fixed parameter clique and dominating set Theoret. Comput. Sci. 2004 326 1–3 57-67
[5]
Feige U A threshold of ln n for approximating set cover J. ACM (JACM) 1998 45 4 634-652
[6]
Feldmann AE, Lee E, and Manurangsi P A survey on approximation in parameterized complexity: hardness and algorithms Algorithms 2020 13 6 146
[7]
Hochba DS Approximation algorithms for NP-hard problems ACM SIGACT News 1997 28 2 40-52
[8]
Hochbaum DS and Pathria A Analysis of the greedy approach in problems of maximum k-coverage Naval Res. Logist. (NRL) 1998 45 6 615-627
[9]
Lin, B., Ren, X., Sun, Y., Wang, X.: Constant approximating parameterized k-setcover is w [2]-hard. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 3305–3316. SIAM (2023)
[10]
Manurangsi, P.: Tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem). In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 62–81. SIAM (2020)
[11]
Nemhauser GL, Wolsey LA, and Fisher ML An analysis of approximations for maximizing submodular set functions-i Math. Program. 1978 14 265-294
[12]
Puatracscu, M., Williams, R.: On the possibility of faster SAT algorithms. In: Charikar, M. (ed.) Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, 17–19 January 2010, pp. 1065–1075. SIAM (2010).
[13]
Sviridenko M A note on maximizing a submodular set function subject to a knapsack constraint Oper. Res. Lett. 2004 32 1 41-43
Index Terms
- On the Fine-Grained Complexity of Approximating Max k-Coverage
Index terms have been assigned to the content through auto-classification.
Recommendations
An improved analysis of Goemans and Williamson's LP-relaxation for MAX SAT
Foundations of computation theory (FCT 2003)For MAX SAT, which is a well-known NP-hard problem, many approximation algorithms have been proposed. Two types of best approximation algorithms for MAX SAT were proposed by Asano and Williamson: one with best proven performance guarantee 0.7846 and the ...
The Complexity of k-SAT
COCO '99: Proceedings of the Fourteenth Annual IEEE Conference on Computational ComplexityThe problem of k-SAT is to determine if the given k-CNF has a satisfying solution. It is a celebrated open question as to whether it requires exponential time to solve k-SAT for k \geq 3.Define s_k (for k\geq 3) to be the infimum of \{\delta: \mbox{...
How Good is the Goemans--Williamson MAX CUT Algorithm?
The celebrated semidefinite programming algorithm for MAX CUT introduced by Goemans and Williamson was known to have a performance ratio of at least $\alpha=\frac 2 {\pi} \min_{0<\theta\le \pi} \frac \theta {1-\cos \theta}$ ($0.87856<\alpha<0.87857$); ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Jul 2024
346 pages
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 29 December 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 02 Mar 2025