Document Open Access Logo

Parameterized Matroid-Constrained Maximum Coverage

Author François Sellier

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.94.pdf
  • Filesize: 0.69 MB
  • 16 pages

Document Identifiers

Author Details

François Sellier
  • Université Paris Cité, CNRS, IRIF, F-75013, Paris, France
  • MINES ParisTech, Université PSL, F-75006, Paris, France

Funding

This work was funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR).

Acknowledgements

The author thanks Chien-Chung Huang, Claire Mathieu, Eli Upfal, and the anonymous reviewers for their helpful comments.

Cite AsGet BibTex

François Sellier. Parameterized Matroid-Constrained Maximum Coverage. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 94:1-94:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.94

Abstract

In this paper, we introduce the concept of Density-Balanced Subset in a matroid, in which independent sets can be sampled so as to guarantee that (i) each element has the same probability to be sampled, and (ii) those events are negatively correlated. These Density-Balanced Subsets are subsets in the ground set of a matroid in which the traditional notion of uniform random sampling can be extended. We then provide an application of this concept to the Matroid-Constrained Maximum Coverage problem. In this problem, given a matroid ℳ = (V, ℐ) of rank k on a ground set V and a coverage function f on V, the goal is to find an independent set S ∈ ℐ maximizing f(S). This problem is an important special case of the much-studied submodular function maximization problem subject to a matroid constraint; this is also a generalization of the maximum k-cover problem in a graph. In this paper, assuming that the coverage function has a bounded frequency μ (i.e., any element of the underlying universe of the coverage function appears in at most μ sets), we design a procedure, parameterized by some integer ρ, to extract in polynomial time an approximate kernel of size ρ ⋅ k that is guaranteed to contain a 1 - (μ - 1)/ρ approximation of the optimal solution. This procedure can then be used to get a Fixed-Parameter Tractable Approximation Scheme (FPT-AS) providing a 1 - ε approximation in time (μ/ε)^O(k) ⋅ |V|^O(1). This generalizes and improves the results of [Manurangsi, 2019] and [Huang and Sellier, 2022], providing the first FPT-AS working on an arbitrary matroid. Moreover, as the kernel has a very simple characterization, it can be constructed in the streaming setting.

Subject Classification

ACM Subject Classification
  • Theory of computation → Packing and covering problems
  • Theory of computation → Fixed parameter tractability
Keywords
  • Matroids
  • approximate kernel
  • maximum coverage

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alexander A. Ageev and Maxim Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. J. Comb. Optim., 8(3):307-328, 2004. URL: https://doi.org/10.1023/B:JOCO.0000038913.96607.c2.
  2. Édouard Bonnet, Vangelis Th. Paschos, and Florian Sikora. Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems. RAIRO Theor. Informatics Appl., 50(3):227-240, 2016. URL: https://doi.org/10.1051/ita/2016022.
  3. Gruia Călinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput., 40(6):1740-1766, 2011. URL: https://doi.org/10.1137/080733991.
  4. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 575-584. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.60.
  5. Jack Edmonds. Minimum partition of a matroid into independent subsets. J. Res. Nat. Bur. Standards Sect. B, 69:67-72, 1965. Google Scholar
  6. Jack Edmonds. Matroids and the greedy algorithm. Mathematical Programming, 1(1):127-136, 1971. URL: http://www.springerlink.com.myaccess.library.utoronto.ca/content/j17526433u12202x/.
  7. Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634-652, 1998. URL: https://doi.org/10.1145/285055.285059.
  8. Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, and Pasin Manurangsi. A survey on approximation in parameterized complexity: Hardness and algorithms. Algorithms, 13(6):146, 2020. URL: https://doi.org/10.3390/a13060146.
  9. Yuval Filmus and Justin Ward. The power of local search: Maximum coverage over a matroid. In Christoph Dürr and Thomas Wilke, editors, 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France, volume 14 of LIPIcs, pages 601-612. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. URL: https://doi.org/10.4230/LIPIcs.STACS.2012.601.
  10. Yuval Filmus and Justin Ward. Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput., 43(2):514-542, 2014. URL: https://doi.org/10.1137/130920277.
  11. Jiong Guo, Rolf Niedermeier, and Sebastian Wernicke. Parameterized complexity of generalized vertex cover problems. In Frank K. H. A. Dehne, Alejandro López-Ortiz, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures, 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings, volume 3608 of Lecture Notes in Computer Science, pages 36-48. Springer, 2005. URL: https://doi.org/10.1007/11534273_5.
  12. Dorit S Hochbaum and Anu Pathria. Analysis of the greedy approach in problems of maximum k-coverage. Naval Research Logistics (NRL), 45(6):615-627, 1998. Google Scholar
  13. Chien-Chung Huang and François Sellier. Matroid-constrained maximum vertex cover: Approximate kernels and streaming algorithms. In Artur Czumaj and Qin Xin, editors, 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022, June 27-29, 2022, Tórshavn, Faroe Islands, volume 227 of LIPIcs, pages 27:1-27:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.SWAT.2022.27.
  14. Chien-Chung Huang and François Sellier. Matroid-constrained vertex cover. Theor. Comput. Sci., 965:113977, 2023. URL: https://doi.org/10.1016/j.tcs.2023.113977.
  15. Chien-Chung Huang and Justin Ward. FPT-algorithms for the l-matchoid problem with linear and submodular objectives. CoRR, abs/2011.06268, 2020. URL: https://arxiv.org/abs/2011.06268.
  16. Naoyuki Kamiyama. A note on robust subsets of transversal matroids. CoRR, abs/2210.09534, 2022. URL: https://doi.org/10.48550/arXiv.2210.09534.
  17. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 224-237. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055456.
  18. Pasin Manurangsi. A note on max k-vertex cover: Faster fpt-as, smaller approximate kernel and improved approximation. In Jeremy T. Fineman and Michael Mitzenmacher, editors, 2nd Symposium on Simplicity in Algorithms, SOSA 2019, January 8-9, 2019, San Diego, CA, USA, volume 69 of OASIcs, pages 15:1-15:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/OASIcs.SOSA.2019.15.
  19. Pasin Manurangsi. 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 Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 62-81. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.5.
  20. Dániel Marx. Parameterized complexity and approximation algorithms. Comput. J., 51(1):60-78, 2008. URL: https://doi.org/10.1093/comjnl/bxm048.
  21. Andrew McGregor, David Tench, and Hoa T. Vu. Maximum coverage in the data stream model: Parameterized and generalized. In Ke Yi and Zhewei Wei, editors, 24th International Conference on Database Theory, ICDT 2021, March 23-26, 2021, Nicosia, Cyprus, volume 186 of LIPIcs, pages 12:1-12:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICDT.2021.12.
  22. George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions—i. Mathematical programming, 14(1):265-294, 1978. Google Scholar
  23. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science & Business Media, 2003. Google Scholar
  24. Piotr Skowron. FPT approximation schemes for maximizing submodular functions. Inf. Comput., 257:65-78, 2017. URL: https://doi.org/10.1016/j.ic.2017.10.002.
  25. Piotr Krzysztof Skowron and Piotr Faliszewski. Fully proportional representation with approval ballots: Approximating the maxcover problem with bounded frequencies in FPT time. In Blai Bonet and Sven Koenig, editors, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, January 25-30, 2015, Austin, Texas, USA, pages 2124-2130. AAAI Press, 2015. URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9674.
  26. Aravind Srinivasan. Distributions on level-sets with applications to approximation algorithms. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 588-597. IEEE Computer Society, 2001. URL: https://doi.org/10.1109/SFCS.2001.959935.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact