Abstract
In the classic maximum coverage problem, we are given subsets \(T_1, \dots , T_m\) of a universe [n] along with an integer k and the objective is to find a subset \(S \subseteq [m]\) of size k that maximizes \(C(S) := |\cup _{i \in S} T_i|\). It is well-known that the greedy algorithm for this problem achieves an approximation ratio of \((1-e^{-1})\) and there is a matching inapproximability result. We note that in the maximum coverage problem if an element \(e \in [n]\) is covered by several sets, it is still counted only once. By contrast, if we change the problem and count each element e as many times as it is covered, then we obtain a linear objective function, \(C^{(\infty )}(S) = \sum _{i \in S} |T_i|\), which can be easily maximized under a cardinality constraint.
We study the maximum \(\ell \)-multi-coverage problem which naturally interpolates between these two extremes. In this problem, an element can be counted up to \(\ell \) times but no more; hence, we consider maximizing the function \(C^{(\ell )}(S) = \sum _{e \in [n]} \min \{\ell , |\{i \in S : e \in T_i\}| \}\), subject to the constraint \(|S| \le k\). Note that the case of \(\ell = 1\) corresponds to the standard maximum coverage setting and \(\ell = \infty \) gives us a linear objective.
We develop an efficient approximation algorithm that achieves an approximation ratio of \(1 - \frac{\ell ^{\ell }e^{-\ell }}{\ell !}\) for the \(\ell \)-multi-coverage problem. In particular, when \(\ell = 2\), this factor is \(1-2e^{-2} \approx 0.73\) and as \(\ell \) grows the approximation ratio behaves as \(1 - \frac{1}{\sqrt{2\pi \ell }}\). We also prove that this approximation ratio is tight, i.e., establish a matching hardness-of-approximation result, under the Unique Games Conjecture.
This problem is motivated by the question of finding a code that optimizes the list-decoding success probability for a given noisy channel. We show how the multi-coverage problem can be relevant in other contexts, such as combinatorial auctions.
A full version of the paper containing the proofs can be found in [3]. This research is supported by the French ANR project ANR-18-CE47-0011 (ACOM). Siddharth Barman gratefully acknowledges the support of a Ramanujan Fellowship (SERB - SB/S2/RJN-128/2015) and a Pratiksha Trust Young Investigator Award. Part of this work was conducted during the first author’s visit to École Normale Supérieure de Lyon and was supported by the Administration de la recherche (ADRE), France.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Here, the Poisson distribution stochastically dominates the binomial. Hence, instead of a lower bound, we obtain an upper bound.
- 2.
That is, a lower bound for the \(\ell \)-coverage value of the size-k set \(\{i \in [m] : x^{\mathrm {int}}_i = 1 \}\).
- 3.
Recall that if X and Y are independent, Poisson random variables with rate parameters \(\lambda _1\) and \(\lambda _2\), respectively, then \(X+Y\) is Poisson-distributed with parameter \(\lambda _1 + \lambda _2\).
References
Ageev, A.A., Sviridenko, M.I.: Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8(3), 307–328 (2004)
Barman, S., Fawzi, O.: Algorithmic aspects of optimal channel coding. IEEE Trans. Inform. Theory (2018). arXiv:1508.04095
Barman, S., Fawzi, O., Ghoshal, S., Gürpınar, E.: Tight approximation bounds for maximum multi-coverage (2019). arXiv:1905.00640
Berman, P., DasGupta, B., Sontag, E.: Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Discrete Appl. Math. 155(6), 733–749 (2007). https://doi.org/10.1016/j.dam.2004.11.009. http://www.sciencedirect.com/science/article/pii/S0166218X06003659. Computational Molecular Biology Series, Issue V
Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740–1766 (2011)
Chekuri, C., Clarkson, K.L., Har-Peled, S.: On the set multicover problem in geometric settings. ACM Trans. Algorithms (TALG) 9(1), 9 (2012)
Conforti, M., Cornuéjols, G.: Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl. Math. 7(3), 251–274 (1984)
Cornuejols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manag. Sci. 23(8), 789–810 (1977). https://doi.org/10.1287/mnsc.23.8.789
Dobson, G.: Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Math. Oper. Res. 7(4), 515–531 (1982)
Dobzinski, S., Schapira, M.: An improved approximation algorithm for combinatorial auctions with submodular bidders. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 1064–1073. Society for Industrial and Applied Mathematics (2006)
Dughmi, S., Roughgarden, T., Yan, Q.: Optimal mechanisms for combinatorial auctions and combinatorial public projects via convex rounding. J. ACM (JACM) 63(4), 30 (2016)
Dughmi, S., Vondrák, J.: Limitations of randomized mechanisms for combinatorial auctions. In: Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), pp. 502–511. IEEE Computer Society, Washington, DC (2011). https://doi.org/10.1109/FOCS.2011.64
Feige, U.: A threshold of ln \(n\) for approximating set cover. J. ACM 45(4), 634–652 (1998)
Feige, U.: On maximizing welfare when utility functions are subadditive. SIAM J. Comput. 39(1), 122–142 (2009)
Feldman, V., Kothari, P.: Learning coverage functions and private release of marginals. In: Conference on Learning Theory, pp. 679–702 (2014)
Hochbaum, D.S.: Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. In: Approximation Algorithms for NP-Hard Problem, pp. 94–143. PWS Pub. (1997)
Hua, Q.-S., Yu, D., Lau, F.C.M., Wang, Y.: Exact algorithms for set multicover and multiset multicover problems. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 34–44. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10631-6_6
Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256–278 (1974)
Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pp. 767–775. ACM (2002)
Khot, S., Vishnoi, N.K.: On the unique games conjecture. In: FOCS, vol. 5, p. 3 (2005)
Krause, A., Golovin, D.: Submodular function maximization. In: Tractability: Practical Approaches to Hard Problems, vol. 3, p. 19 (2012)
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions. Math. Program. 14(1), 265–294 (1978)
Polyanskiy, Y., Poor, H.V., Verdú, S.: Channel coding rate in the finite blocklength regime. IEEE Trans. Inf. Theory 56(5), 2307–2359 (2010)
Rajagopalan, S., Vazirani, V.V.: Primal-dual RNC approximation algorithms for set cover and covering integer programs. SIAM J. Comput. 28(2), 525–540 (1998)
Shaked, M., Shanthikumar, J.G.: Stochastic Orders. Springer, New York (2007). https://doi.org/10.1007/978-0-387-34675-5
Sviridenko, M., Vondrák, J., Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4), 1197–1218 (2017)
Vondrák, J.: Submodularity in combinatorial optimization (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Barman, S., Fawzi, O., Ghoshal, S., Gürpınar, E. (2020). Tight Approximation Bounds for Maximum Multi-coverage. In: Bienstock, D., Zambelli, G. (eds) Integer Programming and Combinatorial Optimization. IPCO 2020. Lecture Notes in Computer Science(), vol 12125. Springer, Cham. https://doi.org/10.1007/978-3-030-45771-6_6
Download citation
DOI: https://doi.org/10.1007/978-3-030-45771-6_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-45770-9
Online ISBN: 978-3-030-45771-6
eBook Packages: Computer ScienceComputer Science (R0)