Document Open Access Logo

Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints

Authors Chien-Chung Huang, Theophile Thiery, Justin Ward

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.62.pdf
  • Filesize: 0.57 MB
  • 19 pages

Document Identifiers

Author Details

Chien-Chung Huang
  • CNRS, DI ENS, Université PSL, Paris, France
Theophile Thiery
  • School of Mathematical Sciences, Queen Mary University of London, UK
Justin Ward
  • School of Mathematical Sciences, Queen Mary University of London, UK

Funding

  • Huang, Chien-Chung: This work was funded by the grants ANR-19-CE48-0016 and ANR-18-CE40-0025-01 from the French National Research Agency (ANR).
  • Ward, Justin: This work was supported by EPSRC New Investigator Award EP/T006781/1.

Cite As Get BibTex

Chien-Chung Huang, Theophile Thiery, and Justin Ward. Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.62

Abstract

We give improved multi-pass streaming algorithms for the problem of maximizing a monotone or arbitrary non-negative submodular function subject to a general p-matchoid constraint in the model in which elements of the ground set arrive one at a time in a stream. The family of constraints we consider generalizes both the intersection of p arbitrary matroid constraints and p-uniform hypergraph matching. For monotone submodular functions, our algorithm attains a guarantee of p+1+ε using O(p/ε)-passes and requires storing only O(k) elements, where k is the maximum size of feasible solution. This immediately gives an O(1/ε)-pass (2+ε)-approximation for monotone submodular maximization in a matroid and (3+ε)-approximation for monotone submodular matching. Our algorithm is oblivious to the choice ε and can be stopped after any number of passes, delivering the appropriate guarantee. We extend our techniques to obtain the first multi-pass streaming algorithms for general, non-negative submodular functions subject to a p-matchoid constraint. We show that a randomized O(p/ε)-pass algorithm storing O(p³klog(k)/ε³) elements gives a (p+1+γ+O(ε))-approximation, where γ is the guarantee of the best-known offline algorithm for the same problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
  • Theory of computation → Approximation algorithms analysis
Keywords
  • submodular maximization
  • streaming algorithms
  • matroid
  • matchoid

Metrics

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

References

  1. Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming submodular maximization: massive data summarization on the fly. In Proc. ACM International Conference on Knowledge Discovery and Data Mining (KDD), pages 671-680, 2014. Google Scholar
  2. Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1497-1514, 2013. Google Scholar
  3. Niv Buchbinder and Moran Feldman. Constrained submodular maximization via a nonsymmetric technique. Mathematics of Operations Research, 44(3):988-1005, 2019. Google Scholar
  4. Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1433-1452, 2014. Google Scholar
  5. Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6):1740-1766, 2011. Google Scholar
  6. Amit Chakrabarti and Sagar Kale. Submodular maximization meets streaming: matchings, matroids, and more. Mathematical Programming, 154(1-2):225-247, 2015. Google Scholar
  7. Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. Streaming algorithms for submodular function maximization. In Proc. International Colloquium on Automata, Languages, and Programming (ICALP), pages 318-330, 2015. Google Scholar
  8. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing, 43(6):1831-1879, 2014. Google Scholar
  9. Uriel Feige. A threshold of ln n for approximating set cover. Journal of the ACM, 45(4):634-652, 1998. Google Scholar
  10. Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular functions. SIAM Journal on Computing, 40(4):1133-1153, 2011. Google Scholar
  11. Moran Feldman, Amin Karbasi, and Ehsan Kazemi. Do less, get more: streaming submodular maximization with subsampling. In Advances in Neural Information Processing Systems (NeurIPS), pages 732-742, 2018. Google Scholar
  12. Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. In Proc. IEEE Symposium on Foundations of Computer Science, (FOCS), pages 570-579, 2011. Google Scholar
  13. Moran Feldman, Joseph (Seffi) Naor, Roy Schwartz, and Justin Ward. Improved approximations for k-exchange systems. In Proc. European Symposium on Algorithms (ESA), pages 784-798, 2011. Google Scholar
  14. Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. The one-way communication complexity of submodular maximization with applications to streaming and robustness. In Proc. ACM Symposium on Theory of Computing (STOC), pages 1363-1374, 2020. Google Scholar
  15. M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey. An analysis of approximations for maximizing submodular set functions II. Mathematical Programming Study, 8:73-87, 1978. Google Scholar
  16. Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1098-1116, 2011. Google Scholar
  17. Chien-Chung Huang and Naonori Kakimura. Multi-pass streaming algorithms for monotone submodular function maximization. CoRR, abs/1802.06212, 2018. URL: http://arxiv.org/abs/1802.06212.
  18. Jon Lee, Maxim Sviridenko, and Jan Vondrák. Submodular maximization over multiple matroids via generalized exchange properties. Mathematics of Operations Research, 35(4):795-806, 2010. Google Scholar
  19. Hui Lin and Jeff Bilmes. Multi-document summarization via budgeted maximization of submodular functions. In Proc. Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), pages 912-920, 2010. Google Scholar
  20. Andrew McGregor and Hoa T. Vu. Better streaming algorithms for the maximum coverage problem. Theory of Computing Systems, 63(7):1595-1619, 2019. Google Scholar
  21. Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Aamin Karbasi. Fast constrained submodular maximization: Personalized data summarization. In Proc. International Conference on Machine Learning (ICML), pages 1358-1367, 2016. Google Scholar
  22. Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. In Proc. AAAI Conference on Artificial Intelligence (AAAI), pages 1812-1818, 2015. Google Scholar
  23. Baharan Mirzasoleiman, Stefanie Jegelka, and Andreas Krause. Streaming non-monotone submodular maximization: Personalized video summarization on the fly. In Proc. AAAI Conference on Artificial Intelligence (AAAI), pages 1379-1386, 2018. Google Scholar
  24. 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
  25. Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrović, Amir Zandieh, Aida Mousavifar, and Ola Svensson. Beyond 1/2-approximation for submodular maximization on massive data streams. In Proc. International Conference on Machine Learning (ICML), pages 3826-3835, 2018. 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 About DROPS Imprint Privacy Contact