Document Open Access Logo

Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints

Authors Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, Andrew Suh

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.6.pdf
  • Filesize: 0.61 MB
  • 19 pages

Document Identifiers

Author Details

Naor Alaluf
  • Department of Mathematics and Computer Science, Open University of Israel, Ra'anana, Israel
Alina Ene
  • Department of Computer Science, Boston University, MA, USA
Moran Feldman
  • Department of Computer Science, University of Haifa, Israel
Huy L. Nguyen
  • Khoury College of Computer and Information Science, Northeastern University, Boston, MA, USA
Andrew Suh
  • Department of Computer Science, Boston University, MA, USA

Funding

  • Alaluf, Naor: The work of Naor Alaluf was supported in part by ISF grant number 1357/16.
  • Ene, Alina: The work of Alina Ene was supported in part by NSF CAREER grant CCF-1750333, NSF grant CCF-1718342, and NSF grant III-1908510.
  • Feldman, Moran: The work of Moran Feldman was supported in part by ISF grant number 1357/16.
  • Nguyen, Huy L.: The work of Huy L. Nguyen was supported in part by NSF CAREER grant CCF-1750716 and NSF grant CCF-1909314.
  • Suh, Andrew: The work of Andrew Suh was supported in part by NSF CAREER grant CCF-1750333, NSF grant CCF-1718342, and NSF grant III-1908510.

Cite As Get BibTex

Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh. Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.6

Abstract

We study the problem of maximizing a non-monotone submodular function subject to a cardinality constraint in the streaming model. Our main contributions are two single-pass (semi-)streaming algorithms that use Õ(k)⋅poly(1/ε) memory, where k is the size constraint. At the end of the stream, both our algorithms post-process their data structures using any offline algorithm for submodular maximization, and obtain a solution whose approximation guarantee is α/(1+α)-ε, where α is the approximation of the offline algorithm. If we use an exact (exponential time) post-processing algorithm, this leads to 1/2-ε approximation (which is nearly optimal). If we post-process with the algorithm of [Niv Buchbinder and Moran Feldman, 2019], that achieves the state-of-the-art offline approximation guarantee of α = 0.385, we obtain 0.2779-approximation in polynomial time, improving over the previously best polynomial-time approximation of 0.1715 due to [Feldman et al., 2018]. One of our algorithms is combinatorial and enjoys fast update and overall running times. Our other algorithm is based on the multilinear extension, enjoys an improved space complexity, and can be made deterministic in some settings of interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
  • Mathematics of computing → Combinatorial optimization
  • Mathematics of computing → Probabilistic algorithms
Keywords
  • Submodular maximization
  • streaming algorithms
  • cardinality constraint

Metrics

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

Related Versions

References

  1. Naor Alaluf and Moran Feldman. Making a sieve random: Improved semi-streaming algorithm for submodular maximization under a cardinality constraint. CoRR, abs/1906.11237, 2019. URL: http://arxiv.org/abs/1906.11237.
  2. Ashwinkumar Badanidiyuru, Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Streaming submodular maximization: Massive data summarization on the fly. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 671-680. ACM, 2014. Google Scholar
  3. Rafael da Ponte Barbosa, Alina Ene, Huy L Nguyen, and Justin Ward. A new framework for distributed submodular maximization. In IEEE Foundations of Computer Science (FOCS), pages 645-654, 2016. Google Scholar
  4. Rafael D.P. Barbosa, Alina Ene, Huy L. Nguyen, and Justin Ward. The power of randomization: Distributed submodular maximization on massive datasets. In International Conference on Machine Learning (ICML), 2015. Google Scholar
  5. Niv Buchbinder and Moran Feldman. Constrained submodular maximization via a non-symmetric technique. Mathematics of Operations Research, 44(3):988-1005, 2019. Google Scholar
  6. Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In SODA, pages 1433-1452, 2014. URL: https://doi.org/10.1137/1.9781611973402.106.
  7. Niv Buchbinder, Moran Feldman, and Roy Schwartz. Online submodular maximization with preemption. ACM Trans. Algorithms, 15(3):30:1-30:31, 2019. URL: https://doi.org/10.1145/3309764.
  8. 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.
  9. Amit Chakrabarti and Sagar Kale. Submodular maximization meets streaming: Matchings, matroids, and more. Mathematical Programming, 154(1-2):225-247, 2015. Google Scholar
  10. Chandra Chekuri. Personal communication, 2018. Google Scholar
  11. Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. Streaming algorithms for submodular function maximization. In International Colloquium on Automata, Languages and Programming (ICALP), pages 318-330. Springer, 2015. Google Scholar
  12. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In FOCS, pages 575-584, 2010. URL: https://doi.org/10.1109/FOCS.2010.60.
  13. Alina Ene and Huy L Nguyen. Constrained submodular maximization: Beyond 1/e. In IEEE Foundations of Computer Science (FOCS), pages 248-257. IEEE, 2016. Google Scholar
  14. Alessandro Epasto, Vahab Mirrokni, and Morteza Zadimoghaddam. Bicriteria distributed submodular maximization in a few rounds. In PACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 25-33, 2017. Google Scholar
  15. 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
  16. Moran Feldman, Christopher Harshaw, and Amin Karbasi. Greed is good: Near-optimal submodular maximization via greedy optimization. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, pages 758-784, 2017. URL: http://proceedings.mlr.press/v65/feldman17b.html.
  17. 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
  18. Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. In IEEE Foundations of Computer Science (FOCS), 2011. URL: https://doi.org/10.1109/FOCS.2011.46.
  19. Moran Feldman, Ashkan Norouzi-Fard, Ola Svensson, and Rico Zenklusen. The one-way communication complexity of submodular maximization with applications to streaming and robustness, 2020. To appear in STOC 2020. Google Scholar
  20. Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011. Google Scholar
  21. Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In ICML, pages 3311-3320, 2019. URL: http://proceedings.mlr.press/v97/kazemi19a.html.
  22. Ravi Kumar, Benjamin Moseley, Sergei Vassilvitskii, and Andrea Vattani. Fast greedy algorithms in mapreduce and streaming. In PACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 1-10, 2013. Google Scholar
  23. Jon Lee, Vahab S Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. Non-monotone submodular maximization under matroid and knapsack constraints. In ACM Symposium on Theory of Computing (STOC), pages 323-332, 2009. Google Scholar
  24. 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
  25. László Lovász. Submodular functions and convexity. In Mathematical Programming The State of the Art, XIth International Symposium on Mathematical Programming, Bonn, Germany, August 23-27, 1982, pages 235-257, 1982. URL: https://doi.org/10.1007/978-3-642-68874-4_10.
  26. Vahab Mirrokni and Morteza Zadimoghaddam. Randomized composable core-sets for distributed submodular maximization. In ACM Symposium on Theory of Computing (STOC), 2015. Google Scholar
  27. Baharan Mirzasoleiman, Stefanie Jegelka, and Andreas Krause. Streaming non-monotone submodular maximization: Personalized video summarization on the fly. In Thirty-second AAAI conference on artificial intelligence, 2018. Google Scholar
  28. Baharan Mirzasoleiman, Amin Karbasi, Ashwinkumar Badanidiyuru, and Andreas Krause. Distributed submodular cover: Succinctly summarizing massive data. In Advances in Neural Information Processing Systems, pages 2881-2889, 2015. Google Scholar
  29. Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed submodular maximization: Identifying representative elements in massive data. In Advances in Neural Information Processing Systems (NeurIPS), pages 2049-2057, 2013. Google Scholar
  30. 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
  31. Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrovic, Amir Zandieh, Aidasadat Mousavifar, and Ola Svensson. Beyond 1/2-approximation for submodular maximization on massive data streams. In International Conference on Machine Learning, pages 3826-3835, 2018. Google Scholar
  32. Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM J. Comput., 42(1):265-304, 2013. URL: https://doi.org/10.1137/110832318.
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