Document Open Access Logo

Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint

Authors Alina Ene, Huy L. Nguyen

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.54.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Alina Ene
  • Department of Computer Science, Boston University, MA, USA
Huy L. Nguyen
  • College of Computer and Information Science, Northeastern University, Boston, MA, USA

Funding

  • Ene, Alina: Partially supported by NSF CAREER grant CCF-1750333 and NSF grant CCF-1718342.
  • Nguyen, Huy L.: Partially supported by NSF CAREER grant CCF-1750716.

Acknowledgements

This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing.

Cite AsGet BibTex

Alina Ene and Huy L. Nguyen. Towards Nearly-Linear Time Algorithms for Submodular Maximization with a Matroid Constraint. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.54

Abstract

We consider fast algorithms for monotone submodular maximization subject to a matroid constraint. We assume that the matroid is given as input in an explicit form, and the goal is to obtain the best possible running times for important matroids. We develop a new algorithm for a general matroid constraint with a 1 - 1/e - epsilon approximation that achieves a fast running time provided we have a fast data structure for maintaining an approximately maximum weight base in the matroid through a sequence of decrease weight operations. We construct such data structures for graphic matroids and partition matroids, and we obtain the first algorithms for these classes of matroids that achieve a nearly-optimal, 1 - 1/e - epsilon approximation, using a nearly-linear number of function evaluations and arithmetic operations.

Subject Classification

ACM Subject Classification
  • Theory of computation → Submodular optimization and polymatroids
Keywords
  • submodular maximization
  • matroid constraints
  • fast running times

Metrics

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

Related Versions

References

  1. Alexander Ageev and Maxim Sviridenko. Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee. Journal of Combinatorial Optimization, 8(3):307-328, 2004. Google Scholar
  2. Yossi Azar and Iftah Gamzu. Efficient Submodular Function Maximization under Linear Packing Constraints. In International Colloquium on Automata, Languages and Programming (ICALP), 2012. Google Scholar
  3. Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014. Google Scholar
  4. Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular Maximization with Cardinality Constraints. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014. Google Scholar
  5. Niv Buchbinder, Moran Feldman, and Roy Schwartz. Comparing Apples and Oranges: Query Trade-off in Submodular Maximization. Math. Oper. Res., 42(2):308-329, 2017. Google Scholar
  6. Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a Submodular Set Function Subject to a Matroid Constraint. SIAM Journal on Computing, 40(6):1740-1766, 2011. Google Scholar
  7. Chandra Chekuri, T. S. Jayram, and Jan Vondrák. On Multiplicative Weight Updates for Concave and Submodular Function Maximization. In Conference on Innovations in Theoretical Computer Science (ITCS), 2015. URL: http://dx.doi.org/10.1145/2688073.2688086.
  8. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures. In IEEE Foundations of Computer Science (FOCS), pages 575-584. IEEE Computer Society, 2010. Google Scholar
  9. Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan. Revenue Submodularity. Theory of Computing, 8(1):95-119, 2012. Google Scholar
  10. Uriel Feige. A threshold of ln n for approximating set cover. jacm, 45:634-652, 1998. Google Scholar
  11. Yuval Filmus and Justin Ward. Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search. SIAM Journal on Computing, 43(2):514-542, 2014. Google Scholar
  12. M L Fisher, G L Nemhauser, and L A Wolsey. An analysis of approximations for maximizing submodular set functions - II. Mathematical Programming Studies, 8:73-87, 1978. Google Scholar
  13. Bernard A Galler and Michael J Fisher. An improved equivalence algorithm. Communications of the ACM, 7(5):301-303, 1964. Google Scholar
  14. Ryan Gomes and Andreas Krause. Budgeted Nonparametric Learning from Data Streams. In International Conference on Machine Learning (ICML), pages 391-398, 2010. Google Scholar
  15. Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM (JACM), 48(4):723-760, 2001. Google Scholar
  16. David Kempe, Jon M. Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 137-146, 2003. Google Scholar
  17. Andreas Krause, Ajit Paul Singh, and Carlos Guestrin. Near-Optimal Sensor Placements in Gaussian Processes: Theory, Efficient Algorithms and Empirical Studies. Journal of Machine Learning Research, 9:235-284, 2008. Google Scholar
  18. Hui Lin and Jeff A. Bilmes. Multi-document Summarization via Budgeted Maximization of Submodular Functions. In Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics, pages 912-920, 2010. Google Scholar
  19. Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier Than Lazy Greedy. In AAAI Conference on Artificial Intelligence (AAAI), 2015. Google Scholar
  20. G L Nemhauser and L A Wolsey. Best Algorithms for Approximating the Maximum of a Submodular Set Function. Mathematics of Operations Research, 3(3):177-188, 1978. Google Scholar
  21. G L Nemhauser, L A Wolsey, and M L Fisher. An analysis of approximations for maximizing submodular set functions - I. Mathematical Programming, 14(1):265-294, 1978. Google Scholar
  22. Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. Google Scholar
  23. Robert Endre Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM (JACM), 22(2):215-225, 1975. Google Scholar
  24. Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In ACM Symposium on Theory of Computing (STOC), 2008. Google Scholar
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