Document Open Access Logo

Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint

Authors Chien-Chung Huang, Naonori Kakimura, Yuichi Yoshida

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2017.11.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Chien-Chung Huang
Naonori Kakimura
Yuichi Yoshida

Cite As Get BibTex

Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida. Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.11

Abstract

In this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access only to a small fraction of the data stored in primary memory. For this problem, we propose a (0.363-epsilon)-approximation algorithm, requiring only a single pass through the data; moreover, we propose a (0.4-epsilon)-approximation algorithm requiring a constant number of passes through the data. The required memory space of both algorithms depends only on the size of the knapsack capacity and epsilon.

Subject Classification

Keywords
  • submodular functions
  • single-pass streaming
  • multiple-pass streaming
  • constant approximation

Metrics

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

References

  1. Noga Alon, Iftah Gamzu, and Moshe Tennenholtz. Optimizing budget allocation among channels and influencers. In Proceedings of the 21st International Conference on World Wide Web (WWW), pages 381-388, 2012. Google Scholar
  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 (KDD), pages 671-680, 2014. Google Scholar
  3. Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1497-1514, 2013. Google Scholar
  4. 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
  5. Amit Chakrabarti and Sagar Kale. Submodular maximization meets streaming: matchings, matroids, and more. Mathematical Programming, 154(1-2):225-247, 2015. URL: http://dx.doi.org/10.1007/s10107-015-0900-7.
  6. T.-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang, and Zhihao Gavin Tang. Online submodular maximization with free disposal: Randomization beats for partition matroids online. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1204-1223, 2017. Google Scholar
  7. Chandra Chekuri, Shalmoli Gupta, and Kent Quanrud. Streaming algorithms for submodular function maximization. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), volume 9134, 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. URL: http://dx.doi.org/10.1137/110839655.
  9. Yuval Filmus and Justin Ward. A tight combinatorial algorithm for submodular maximization subject to a matroid constraint. SIAM Journal on Computing, 43(2):514-542, 2014. Google Scholar
  10. 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
  11. David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 137-146, 2003. Google Scholar
  12. 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
  13. Ariel Kulik, Hadas Shachnai, and Tami Tamir. Maximizing submodular set functions subject to multiple linear constraints. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 545-554, 2013. Google Scholar
  14. Jon Lee. Maximum Entropy Sampling, volume 3 of Encyclopedia of Environmetrics, pages 1229-1234. John Wiley & Sons, Ltd., 2006. Google Scholar
  15. 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
  16. Hui Lin and Jeff Bilmes. Multi-document summarization via budgeted maximization of submodular functions. In Proceedings of the 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), pages 912-920, 2010. Google Scholar
  17. Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL-HLT), pages 510-520, 2011. Google Scholar
  18. Tasuku Soma, Naonori Kakimura, Kazuhiro Inaba, and Ken-ichi Kawarabayashi. Optimal budget allocation: Theoretical guarantee and efficient algorithm. In Proceedings of the 31st International Conference on Machine Learning (ICML), pages 351-359, 2014. Google Scholar
  19. Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 32(1):41-43, 2004. Google Scholar
  20. Laurence Wolsey. Maximising real-valued submodular functions: primal and dual heuristics for location problems. Mathematics of Operations Research, 1982. Google Scholar
  21. Qilian Yu, Easton Li Xu, and Shuguang Cui. Streaming algorithms for news and scientific literature recommendation: Submodular maximization with a d-knapsack constraint. IEEE Global Conference on Signal and Information Processing, 2016. 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