Top

Theory of Computing Systems

Published in:

09-11-2021

Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization

Authors: Chien-Chung Huang, Naonori Kakimura

Published in: Theory of Computing Systems | Issue 1/2022

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider maximizing a monotone submodular function under a cardinality constraint or a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access to only a small fraction of the data stored in primary memory. We propose the following streaming algorithms taking O(ε^− 1) passes: (1) a (1 − e^− 1 − ε)-approximation algorithm for the cardinality-constrained problem, (2) a (0.5 − ε)-approximation algorithm for the knapsack-constrained problem. Both of our algorithms run deterministically in O^∗(n) time, using O^∗(K) space, where n is the size of the ground set and K is the size of the knapsack. Here the term O^∗ hides a polynomial of \(\log K\) and ε^− 1. Our streaming algorithms can also be used as fast approximation algorithms. In particular, for the cardinality-constrained problem, our algorithm takes \(O(n\varepsilon ^{-1} \log (\varepsilon ^{-1}\log K) )\) time, improving on the algorithm of Badanidiyuru and Vondrák that takes \(O(n \varepsilon ^{-1} \log (\varepsilon ^{-1} K) )\) time.

previous article Stable Multi-Level Monotonic Eroders

next article The Power of the Weighted Sum Scalarization for Approximating Multiobjective Optimization Problems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Independently of our work, Norouzi-Fard et al. [43] proposed another algorithm with the same performance as the second one in Theorem 1

Recently, it is shown in [44] that it suffices to enumerate all the sets of at most two items.

This theorem is essentially a rephrasing of Theorem 5.

Ahn, K.J., Guha, S.: Linear programming in the semi-streaming model with application to the maximum matching problem. Inform. Comput. 222, 59–79 (2013). 38th International Colloquium on Automata Languages and Programming (ICALP 2011)MathSciNetCrossRef

Alaluf, N., Ene, A., Feldman, M., Nguyen, H.L., Suh, A.: Optimal streaming algorithms for submodular maximization with cardinality constraints. In: Czumaj, A., Dawar, A., Merelli, E. (eds.) 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2020.6, vol. 168, pp 6:1–6:19 (2020)

Alon, N., Gamzu, I., Tennenholtz, M.: Optimizing budget allocation among channels and influencers. In: Proceedings of the 21st international conference on world wide web (WWW), pp 381–388 (2012)

Badanidiyuru, A., Mirzasoleiman, B., Karbasi, A., Krause, A.: 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), pp 671–680 (2014)

Badanidiyuru, A., Vondrák, J.: Fast algorithms for maximizing submodular functions. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 1497–1514 (2013)

Balkanski, E., Rubinstein, A., Singer, Y.: An exponential speedup in parallel running time for submodular maximization without loss in approximation. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms SODA, pp 283–302 (2019)

Balkanski, E., Singer, Y.: The adaptive complexity of maximizing a submodular function. In: Proceedings of the 50th Annual ACM Symposium on Theory of Computing, STOC 2018, pp 1138–1151. ACM, New York (2018)

Barbosa, R.D.P., Ene, A., Nguyễn, H.L., Ward, J.: A new framework for distributed submodular maximization. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp 645–654 (2016)

Bateni, M., Esfandiari, H., Mirrokni, V.: Almost optimal streaming algorithms for coverage problems. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, pp 13–23 (2017)

10.

Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740–1766 (2011)MathSciNetCrossRef

11.

Chakrabarti, A., Kale, S.: Submodular maximization meets streaming: matchings, matroids, and more. Math. Program. 154(1-2), 225–247 (2015)MathSciNetCrossRef

12.

Chan, T.H.H., Huang, Z., Jiang, S.H.C., Kang, N., Tang, Z.G.: 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), pp 1204–1223 (2017)

13.

Chan, T.H.H., Jiang, S.H.C., Tang, Z.G., Wu, X.: Online Submodular Maximization Problem with Vector Packing Constraint. In: Annual European Symposium on Algorithms (ESA), pp 24:1–24:14 (2017)

14.

Chekuri, C., Gupta, S., Quanrud, K.: Streaming algorithms for submodular function maximization. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), vol. 9134, pp 318–330 (2015)

15.

Chekuri, C., Quanrud, K.: Submodular function maximization in parallel via the multilinear relaxation. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 303–322 (2019)

16.

Chekuri, C., Vondrák, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6), 1831–1879 (2014)MathSciNetCrossRef

17.

Ene, A., Nguyễn, H.L.: A nearly-linear time algorithm for submodular maximization with a knapsack constraint. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), LIPIcs, vol. 132, pp 53:1–53:12 (2019)

18.

Ene, A., Nguyễn, H.L.: Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms (SODA), pp 274–282 (2019)

19.

Feldman, M., Karbasi, A., Kazemi, E.: Do less, get more: streaming submodular maximization with subsampling. In: Annual Conference on Neural Information Processing Systems (NeurIPS), pp 730–740 (2018)

20.

Feldman, M., Norouzi-Fard, A., Svensson, O., Zenklusen, R.: The one-way communication complexity of submodular maximization with applications to streaming and robustness. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp 1363–1374 (2020)

21.

Filmus, Y., Ward, J.: A tight combinatorial algorithm for submodular maximization subject to a matroid constraint. SIAM J. Comput. 43(2), 514–542 (2014)MathSciNetCrossRef

22.

Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions i. Math. Program., pp. 265–294 (1978)

23.

Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions ii. Math Prog Study 8, 73–87 (1978)MathSciNetCrossRef

24.

Haba, R., Kazemi, E., Feldman, M., Karbasi, A.: Streaming submodular maximization under a k-set system constraint. In: H.D. III, Singh, A (eds.) Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research. PMLR. http://proceedings.mlr.press/v119/haba20a.html, vol. 119, pp 3939–3949 (2020)

25.

Huang, C., Kakimura, N.: Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica 83 (3), 879–902 (2021). https://doi.org/10.1007/s00453-020-00786-4MathSciNetCrossRef

26.

Huang, C.C., Kakimura, N., Mauras, S., Yoshida, Y.: Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model, SIAM Journal on Discrete Mathematics, to appear (2021)

27.

Huang, C.C., Kakimura, N., Yoshida, Y.: Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica 82(4), 1006–1032 (2020)MathSciNetCrossRef

28.

Kale, S., Tirodkar, S.: Maximum matching in two, three, and a few more passes over graph streams. In: The 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX2017) (2017)

29.

Kazemi, E., Mitrovic, M., Zadimoghaddam, M., Lattanzi, S., Karbasi, A.: Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity. In: Proceedings of the 36th International Conference on Machine Learning (ICML), pp 3311–3320 (2019)

30.

Kempe, D., Kleinberg, J., 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), pp 137–146 (2003)

31.

Krause, A., Singh, A.P., Guestrin, C.: Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235–284 (2008)MATH

32.

Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple linear constraints. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp 545–554 (2013)

33.

Kumar, R., Moseley, B., Vassilvitskii, S., Vattani, A.: Fast greedy algorithms in mapreduce and streaming. ACM Trans. Parallel Comput. 2(3), 14:1–14:22 (2015)CrossRef

34.

Lee, J.: Maximum entropy sampling, encyclopedia of environmetrics, vol. 3, pp 1229–1234. Wiley, New York (2006)

35.

Lee, J., Sviridenko, M., Vondrák, J.: Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4), 795–806 (2010)MathSciNetCrossRef

36.

Lin, H., Bilmes, J.: 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), pp 912–920 (2010)

37.

Lin, H., Bilmes, J.: 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), pp 510–520 (2011)

38.

McGregor, A.: Finding graph matchings in data streams. In: Proceedings of the 8th International Workshop on Approximation, Randomization and Combinatorial Optimization Problems, APPROX05, pp 170–181 (2005)

39.

McGregor, A.: Graph stream algorithms: a survey. SIGMOD Rec. 43(1), 9–20 (2014)CrossRef

40.

McGregor, A., Vu, H.T.: Better streaming algorithms for the maximum coverage problem. In: International Conference on Database Theory (ICDT) (2017)

41.

Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondrák, J., Krause, A.: Lazier than lazy greedy. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence, AAAI2015, pp 1812–1818. AAAI Press (2015)

42.

Mirzasoleiman, B., Jegelka, S., Krause, A.: Streaming non-monotone submodular maximization: personalized video summarization on the fly. In: Proc. Conference on Artificial Intelligence (AAAI) (2018)

43.

Norouzi-Fard, A., Tarnawski, J., Mitrovic, S., Zandieh, A., Mousavifar, A., Svensson, O.: Beyond 1/2-approximation for submodular maximization on massive data streams. In: Proceedings of the 35th International Conference on Machine Learning (ICML), pp 3826–3835 (2018)

44.

Nutov, Z., Shoham, E.: Practical budgeted submodular maximization (2020)

45.

da Ponte Barbosa, R., Ene, A., Nguyễn, H.L., Ward, J.: The power of randomization: Distributed submodular maximization on massive datasets. In: Bach, F.R., Blei, D.M. (eds.) Proceedings of the 32nd International Conference on Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, JMLR workshop and conference proceedings. JMLR.org. http://proceedings.mlr.press/v37/barbosa15.html, vol. 37, pp 1236–1244 (2015)

46.

Soma, T., Kakimura, N., Inaba, K., Kawarabayashi, K.: Optimal budget allocation: Theoretical guarantee and efficient algorithm. In: Proceedings of the 31st International Conference on Machine Learning (ICML), pp 351–359 (2014)

47.

Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1), 41–43 (2004)MathSciNetCrossRef

48.

Wolsey, L.: Maximising real-valued submodular functions: primal and dual heuristics for location problems. Math. Oper. Res. (1982)

49.

Yaroslavtsev, G., Zhou, S., Avdiukhin, D.: “Bring Your Own Greedy”+Max: near-optimal 1/2-approximations for submodular knapsack. In: International Conference on Artificial Intelligence and Statistics (AISTATS), pp 3263–3274 (2020)

50.

Yoshida, Y.: Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint. SIAM J. Discrete Math. 33(3), 1452–1471 (2019)MathSciNetCrossRef

51.

Yu, Q., Xu, E.L., Cui, S.: Streaming algorithms for news and scientific literature recommendation: Submodular maximization with a d-knapsack constraint. IEEE Global Conf Signal Inf Process (2016)

Title: Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization
Authors: Chien-Chung Huang
Naonori Kakimura
Publication date: 09-11-2021
Publisher: Springer US
Published in: Theory of Computing Systems / Issue 1/2022
Print ISSN: 1432-4350
Electronic ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-021-10065-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2022

Generating Visual Invariants −a New Approach to Invariant Recognition

The Power of the Weighted Sum Scalarization for Approximating Multiobjective Optimization Problems

Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators

FKT is Not Universal — A Planar Holant Dichotomy for Symmetric Constraints

Stable Multi-Level Monotonic Eroders

An Alternating Algorithm for Finding Linear Arrow-Debreu Market Equilibria

Premium Partner