{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:08Z","timestamp":1750220768945,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":58,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384286","type":"proceedings-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T21:48:36Z","timestamp":1624916916000},"page":"1363-1374","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["The one-way communication complexity of submodular maximization with applications to streaming and robustness"],"prefix":"10.1145","author":[{"given":"Moran","family":"Feldman","sequence":"first","affiliation":[{"name":"University of Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashkan","family":"Norouzi-Fard","sequence":"additional","affiliation":[{"name":"Google Research, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[{"name":"EPFL, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Optimal streaming algorithms for submodular maximization with cardinality constraints. CoRR, abs\/","author":"Alaluf Naor","year":"1911","unstructured":"[AEF+20] Naor Alaluf , Alina Ene , Moran Feldman , Huy L. Nguyen , and Andrew Suh . Optimal streaming algorithms for submodular maximization with cardinality constraints. CoRR, abs\/ 1911 .12959, 2020. [AEF+20] Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh. Optimal streaming algorithms for submodular maximization with cardinality constraints. CoRR, abs\/ 1911.12959, 2020."},{"key":"e_1_3_2_1_2_1","volume-title":"Submodular secretary problem with shortlists. CoRR, abs\/","author":"Agrawal Shipra","year":"1809","unstructured":"[ASS18] Shipra Agrawal , Mohammad Shadravan , and Clif Stein . Submodular secretary problem with shortlists. CoRR, abs\/ 1809 .05082, 2018. [ASS18] Shipra Agrawal, Mohammad Shadravan, and Clif Stein. Submodular secretary problem with shortlists. CoRR, abs\/ 1809.05082, 2018."},{"key":"e_1_3_2_1_3_1","first-page":"118","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS)","volume":"23","author":"Bach Francis R.","year":"2010","unstructured":"[Bac10] Francis R. Bach . Structured sparsity-inducing norms through submodular functions . In Proceedings of Advances in Neural Information Processing Systems (NIPS) , volume 23 , pages 118 - 126 , 2010 . [Bac10] Francis R. Bach. Structured sparsity-inducing norms through submodular functions. In Proceedings of Advances in Neural Information Processing Systems (NIPS), volume 23, pages 118-126, 2010."},{"key":"e_1_3_2_1_4_1","first-page":"645","volume-title":"Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Barbosa Rafael","year":"2016","unstructured":"[BENW16] Rafael Barbosa , Alina Ene , Huy L. Nguyen , and Justin Ward . A new framework for distributed submodular maximization . In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 645 - 654 , 2016 . [BENW16] Rafael Barbosa, Alina Ene, Huy L. Nguyen, and Justin Ward. A new framework for distributed submodular maximization. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 645-654, 2016."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1137\/1.9781611973730.80"},{"unstructured":"[BIRB15] Ramakrishna Bairi Rishabh K. Iyer Ganesh Ramakrishnan and Jef A.  [BIRB15] Ramakrishna Bairi Rishabh K. Iyer Ganesh Ramakrishnan and Jef A.","key":"e_1_3_2_1_6_1"},{"key":"e_1_3_2_1_7_1","first-page":"553","volume-title":"Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (ACL | IJCNLP)","volume":"1","year":"2015","unstructured":"Bilmes. Summarization of multi-document topic hierarchies using submodular mixtures . In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (ACL | IJCNLP) , volume 1 , pages 553 - 563 , 2015 . Bilmes. Summarization of multi-document topic hierarchies using submodular mixtures. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (ACL | IJCNLP), volume 1, pages 553-563, 2015."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.1145\/2623330.2623637"},{"key":"e_1_3_2_1_9_1","first-page":"508","volume-title":"Proceedings of the 34th International Conference on Machine Learning (ICML)","author":"Bogunovic Ilija","year":"2017","unstructured":"[BMSC17] Ilija Bogunovic , Slobodan Mitrovic , Jonathan Scarlett , and Volkan Cevher . Robust submodular maximization: A non-uniform partitioning approach . In Proceedings of the 34th International Conference on Machine Learning (ICML) , pages 508 - 516 , 2017 . [BMSC17] Ilija Bogunovic, Slobodan Mitrovic, Jonathan Scarlett, and Volkan Cevher. Robust submodular maximization: A non-uniform partitioning approach. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 508-516, 2017."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.1137\/1.9781611975482.19"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1145\/3313276.3316304"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1145\/3188745.3188752"},{"unstructured":"[BYJKS02] Ziv Bar-Yossef Thathachar S. Jayram Ravi Kumar and D. Sivakumar.  [BYJKS02] Ziv Bar-Yossef Thathachar S. Jayram Ravi Kumar and D. Sivakumar.","key":"e_1_3_2_1_13_1"},{"key":"e_1_3_2_1_14_1","first-page":"93","volume-title":"Proceedings of the 17th Annual IEEE Conference on Computational Complexity (CCC)","author":"Information","year":"2002","unstructured":"Information theory methods in communication complexity . In Proceedings of the 17th Annual IEEE Conference on Computational Complexity (CCC) , pages 93 - 102 , 2002 . Information theory methods in communication complexity. In Proceedings of the 17th Annual IEEE Conference on Computational Complexity (CCC), pages 93-102, 2002."},{"unstructured":"[CCPV11] Gruia C\u0103linescu Chandra Chekuri Martin P\u00e1l and Jan Vondr\u00e1k.  [CCPV11] Gruia C\u0103linescu Chandra Chekuri Martin P\u00e1l and Jan Vondr\u00e1k.","key":"e_1_3_2_1_15_1"},{"key":"e_1_3_2_1_16_1","first-page":"1740","volume":"40","author":"Maximizing","unstructured":"Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing , 40 ( 6 ): 1740 - 1766 , 2011. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40 ( 6 ): 1740-1766, 2011.","journal-title":"Computing"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1145\/3313276.3316327"},{"unstructured":"[Cha07] A. Chakrabarti. Lower bounds for multi-player pointer jumping.  [Cha07] A. Chakrabarti. Lower bounds for multi-player pointer jumping.","key":"e_1_3_2_1_18_1"},{"unstructured":"Electronic Colloquium on Computational Complexity 14 2007.  Electronic Colloquium on Computational Complexity 14 2007.","key":"e_1_3_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1007\/978-3-319-07557-0_18"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1137\/1.9781611975482.20"},{"key":"e_1_3_2_1_22_1","first-page":"1592","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS)","volume":"25","author":"Das Abhimanyu","year":"2012","unstructured":"[DDK12] Abhimanyu Das , Anirban Dasgupta , and Ravi Kumar . Selecting diverse features via spectral regularization . In Proceedings of Advances in Neural Information Processing Systems (NIPS) , volume 25 , pages 1592 - 1600 , 2012 . [DDK12] Abhimanyu Das, Anirban Dasgupta, and Ravi Kumar. Selecting diverse features via spectral regularization. In Proceedings of Advances in Neural Information Processing Systems (NIPS), volume 25, pages 1592-1600, 2012."},{"key":"e_1_3_2_1_23_1","first-page":"1057","volume-title":"Proceedings of the 28th International Conference on Machine Learning (ICML)","author":"Das Abhimanyu","year":"2011","unstructured":"[DK11] Abhimanyu Das and David Kempe . Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection . In Proceedings of the 28th International Conference on Machine Learning (ICML) , pages 1057 - 1064 , 2011 . [DK11] Abhimanyu Das and David Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proceedings of the 28th International Conference on Machine Learning (ICML), pages 1057-1064, 2011."},{"unstructured":"[dPBENW15] Rafael da Ponte Barbosa Alina Ene Huy L. Nguyen and Justin Ward.  [dPBENW15] Rafael da Ponte Barbosa Alina Ene Huy L. Nguyen and Justin Ward.","key":"e_1_3_2_1_24_1"},{"key":"e_1_3_2_1_25_1","first-page":"1236","volume-title":"Proceedings of the 32nd International Conference on Machine Learning (ICML)","author":"The","year":"2015","unstructured":"The power of randomization: Distributed submodular maximization on massive datasets . In Proceedings of the 32nd International Conference on Machine Learning (ICML) , pages 1236 - 1244 , 2015 . The power of randomization: Distributed submodular maximization on massive datasets. In Proceedings of the 32nd International Conference on Machine Learning (ICML), pages 1236-1244, 2015."},{"unstructured":"[EN19] Alina Ene and Huy L. Nguyen. Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time.  [EN19] Alina Ene and Huy L. Nguyen. Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time.","key":"e_1_3_2_1_26_1"},{"key":"e_1_3_2_1_27_1","first-page":"274","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"In","year":"2019","unstructured":"In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 274 - 282 , 2019 . In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 274-282, 2019."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1145\/3313276.3316389"},{"key":"e_1_3_2_1_29_1","volume-title":"A threshold of ln for approximating set cover. Journal of the ACM (JACM), 45 ( 4 ): 634-652","author":"Feige Uriel","year":"1998","unstructured":"[Fei98] Uriel Feige . A threshold of ln for approximating set cover. Journal of the ACM (JACM), 45 ( 4 ): 634-652 , 1998 . [Fei98] Uriel Feige. A threshold of ln for approximating set cover. Journal of the ACM (JACM), 45 ( 4 ): 634-652, 1998."},{"key":"e_1_3_2_1_30_1","volume-title":"Do less, get more: Streaming submodular maximization with subsampling. CoRR, abs\/","author":"Feldman Moran","year":"1802","unstructured":"[FKK18] Moran Feldman , Amin Karbasi , and Ehsan Kazemi . Do less, get more: Streaming submodular maximization with subsampling. CoRR, abs\/ 1802 .07098, 2018. [FKK18] Moran Feldman, Amin Karbasi, and Ehsan Kazemi. Do less, get more: Streaming submodular maximization with subsampling. CoRR, abs\/ 1802.07098, 2018."},{"unstructured":"[FMZ19a] Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam.  [FMZ19a] Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam.","key":"e_1_3_2_1_31_1"},{"key":"e_1_3_2_1_32_1","first-page":"1833","volume-title":"Proceedings of the 36th International Conference on Machine Learning (ICML)","year":"2019","unstructured":"Non-monotone submodular maximization with nearly optimal adaptivity and query complexity . In Proceedings of the 36th International Conference on Machine Learning (ICML) , pages 1833 - 1842 , 2019 . Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 1833-1842, 2019."},{"unstructured":"[FMZ19b] Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam.  [FMZ19b] Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam.","key":"e_1_3_2_1_33_1"},{"key":"e_1_3_2_1_34_1","first-page":"255","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Submodular","year":"2019","unstructured":"Submodular maximization with nearly optimal approximation, adaptivity and query complexity . In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 255 - 273 , 2019 . Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 255-273, 2019."},{"key":"e_1_3_2_1_35_1","volume-title":"The one-way communication complexity of submodular maximization with applications to streaming and robustness","author":"Feldman Moran","year":"2020","unstructured":"[FNFSZ20] 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 . [FNFSZ20] 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."},{"key":"e_1_3_2_1_36_1","first-page":"45","volume-title":"Proceedings of 46th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Cormode C. Konrad G.","year":"2019","unstructured":"[GC19] C. Konrad G. Cormode , J. Dark . Independent sets in vertex-arrival streams . In Proceedings of 46th International Colloquium on Automata, Languages and Programming (ICALP) , pages 45 : 1-45 : 14, 2019 . [GC19] C. Konrad G. Cormode, J. Dark. Independent sets in vertex-arrival streams. In Proceedings of 46th International Colloquium on Automata, Languages and Programming (ICALP), pages 45 : 1-45 : 14, 2019."},{"key":"e_1_3_2_1_37_1","first-page":"427","volume":"42","author":"Golovin Daniel","unstructured":"[GK11] Daniel Golovin and Andreas Krause . Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artifcial Intelligence Research , 42 ( 1 ): 427 - 486 , 2011. [GK11] Daniel Golovin and Andreas Krause. Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artifcial Intelligence Research, 42 ( 1 ): 427-486, 2011.","journal-title":"Artifcial Intelligence Research"},{"key":"e_1_3_2_1_38_1","volume-title":"Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model. CoRR, abs\/","author":"Huang Chien-Chung","year":"2002","unstructured":"[HKMY20] Chien-Chung Huang , Naonori Kakimura , Simon Mauras , and Yuichi Yoshida . Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model. CoRR, abs\/ 2002 .05477, 2020. [HKMY20] Chien-Chung Huang, Naonori Kakimura, Simon Mauras, and Yuichi Yoshida. Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model. CoRR, abs\/ 2002.05477, 2020."},{"key":"e_1_3_2_1_39_1","volume-title":"The one-way communication complexity of hamming distance. Theory of Computing, 4 ( 1 ): 129-135","author":"Jayram Thathachar S","year":"2008","unstructured":"[JKS08] Thathachar S Jayram , Ravi Kumar , and D Sivakumar . The one-way communication complexity of hamming distance. Theory of Computing, 4 ( 1 ): 129-135 , 2008 . [JKS08] Thathachar S Jayram, Ravi Kumar, and D Sivakumar. The one-way communication complexity of hamming distance. Theory of Computing, 4 ( 1 ): 129-135, 2008."},{"unstructured":"[Kap13] Michael Kapralov. Better bounds for matchings in the streaming model.  [Kap13] Michael Kapralov. Better bounds for matchings in the streaming model.","key":"e_1_3_2_1_40_1"},{"key":"e_1_3_2_1_41_1","first-page":"1679","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"In","year":"2013","unstructured":"In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1679 - 1697 , 2013 . In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1679-1697, 2013."},{"unstructured":"[KMZ+19] 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.  [KMZ+19] 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.","key":"e_1_3_2_1_42_1"},{"key":"e_1_3_2_1_43_1","first-page":"3311","volume-title":"Proceedings of the 36th International Conference on Machine Learning (ICML)","author":"In","year":"2019","unstructured":"In Proceedings of the 36th International Conference on Machine Learning (ICML) , pages 3311 - 3320 , 2019 . In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 3311-3320, 2019."},{"key":"e_1_3_2_1_44_1","first-page":"2544","volume-title":"Proceedings of the 35th International Conference on Machine Learning (ICML)","author":"Kazemi Ehsan","year":"2018","unstructured":"[KZK18] Ehsan Kazemi , Morteza Zadimoghaddam , and Amin Karbasi . Scalable deletion-robust submodular maximization: Data summarization with privacy and fairness constraints . In Proceedings of the 35th International Conference on Machine Learning (ICML) , pages 2544 - 2553 , 2018 . [KZK18] Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Scalable deletion-robust submodular maximization: Data summarization with privacy and fairness constraints. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 2544-2553, 2018."},{"key":"e_1_3_2_1_45_1","first-page":"18","volume-title":"2nd Symposium on Simplicity in Algorithms (SOSA)","author":"Liu Paul","year":"2019","unstructured":"[LV19] Paul Liu and Jan Vondr\u00e1k . Submodular optimization in the mapreduce model . In 2nd Symposium on Simplicity in Algorithms (SOSA) , pages 18 : 1-18 : 10, 2019 . [LV19] Paul Liu and Jan Vondr\u00e1k. Submodular optimization in the mapreduce model. In 2nd Symposium on Simplicity in Algorithms (SOSA), pages 18 : 1-18 : 10, 2019."},{"key":"e_1_3_2_1_46_1","first-page":"4560","volume-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS)","author":"Mitrovi\u0107 Slobodan","year":"2017","unstructured":"[MBNF+17] Slobodan Mitrovi\u0107 , Ilija Bogunovic , Ashkan Norouzi-Fard , Jakub Tarnawski , and Volkan Cevher . Streaming robust submodular maximization: A partitioned thresholding approach . In Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS) , pages 4560 - 4569 , 2017 . [MBNF+17] Slobodan Mitrovi\u0107, Ilija Bogunovic, Ashkan Norouzi-Fard, Jakub Tarnawski, and Volkan Cevher. Streaming robust submodular maximization: A partitioned thresholding approach. In Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS), pages 4560-4569, 2017."},{"key":"e_1_3_2_1_47_1","first-page":"2449","volume-title":"Proceedings of the 34th International Conference on Machine Learning (ICML)","author":"Mirzasoleiman Baharan","year":"2017","unstructured":"[MKK17] Baharan Mirzasoleiman , Amin Karbasi , and Andreas Krause . Deletionrobust submodular maximization: Data summarization with \u201cthe right to be forgotten \u201d. In Proceedings of the 34th International Conference on Machine Learning (ICML) , pages 2449 - 2458 , 2017 . [MKK17] Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. Deletionrobust submodular maximization: Data summarization with \u201cthe right to be forgotten\u201d. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 2449-2458, 2017."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_48_1","DOI":"10.1007\/s00224-018-9878-x"},{"key":"e_1_3_2_1_49_1","first-page":"153","volume-title":"Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC)","author":"Vahab","year":"2015","unstructured":"[MZ15] Vahab S. Mirrokni and Morteza Zadimoghaddam. Randomized composable core-sets for distributed submodular maximization . In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC) , pages 153 - 162 , 2015 . [MZ15] Vahab S. Mirrokni and Morteza Zadimoghaddam. Randomized composable core-sets for distributed submodular maximization. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 153-162, 2015."},{"unstructured":"[NTM+18] 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.  [NTM+18] 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.","key":"e_1_3_2_1_50_1"},{"key":"e_1_3_2_1_51_1","first-page":"3826","volume-title":"Proceedings of the 35th International Conference on Machine Learning (ICML)","author":"In","year":"2018","unstructured":"In Proceedings of the 35th International Conference on Machine Learning (ICML) , pages 3826 - 3835 , 2018 . In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 3826-3835, 2018."},{"key":"e_1_3_2_1_52_1","volume-title":"Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3 ( 3 ): 177-188","author":"Nemhauser George L.","year":"1978","unstructured":"[NW78] George L. Nemhauser and Laurence A. Wolsey . Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3 ( 3 ): 177-188 , 1978 . [NW78] George L. Nemhauser and Laurence A. Wolsey. Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 3 ( 3 ): 177-188, 1978."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_53_1","DOI":"10.1007\/BF01588971"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_54_1","DOI":"10.1007\/978-3-319-33461-5_26"},{"unstructured":"[Sch03] A. Schrijver. Combinatorial Optimization-Polyhedra and Eficiency.  [Sch03] A. Schrijver. Combinatorial Optimization-Polyhedra and Eficiency.","key":"e_1_3_2_1_55_1"},{"unstructured":"Springer 2003.  Springer 2003.","key":"e_1_3_2_1_56_1"},{"unstructured":"[ZJCP14] Jingjing Zheng Zhuolin Jiang Rama Chellappa and P. Jonathon Phillips.  [ZJCP14] Jingjing Zheng Zhuolin Jiang Rama Chellappa and P. Jonathon Phillips.","key":"e_1_3_2_1_57_1"},{"key":"e_1_3_2_1_58_1","first-page":"1341","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS)","volume":"27","author":"Submodular","year":"2014","unstructured":"Submodular attribute selection for action recognition in video . In Proceedings of Advances in Neural Information Processing Systems (NIPS) , volume 27 , pages 1341 - 1349 , 2014 . Submodular attribute selection for action recognition in video. In Proceedings of Advances in Neural Information Processing Systems (NIPS), volume 27, pages 1341-1349, 2014."}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '20","name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA"},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384286","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384286","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":58,"alternative-id":["10.1145\/3357713.3384286","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384286","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}