{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T16:16:40Z","timestamp":1772122600059,"version":"3.50.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T00:00:00Z","timestamp":1691798400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1357\/16"],"award-info":[{"award-number":["1357\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200021-184656"],"award-info":[{"award-number":["200021-184656"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200021_184622 and 200021_165866"],"award-info":[{"award-number":["200021_184622 and 200021_165866"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Union\u2019s Horizon 2020 research and innovation programme","award":["817750"],"award-info":[{"award-number":["817750"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,8,31]]},"abstract":"<jats:p>We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multiplayer model that lies between the offline and streaming model, and study it under the aspect of one-way communication complexity. Our model captures the streaming setting (by considering a large number of players), and, in addition, two-player approximation results for it translate into the robust setting. We present tight one-way communication complexity results for our model, which, due to the connections mentioned previously, have multiple implications in the data stream and robust setting.<\/jats:p>\n          <jats:p>Even for just two players, a prior information-theoretic hardness result implies that no approximation factor above 1\/2 can be achieved in our model, if only queries to feasible sets (i.e., sets respecting the cardinality constraint) are allowed. We show that the possibility of querying infeasible sets can actually be exploited to beat this bound, by presenting a tight 2\/3-approximation taking exponential time, and an efficient 0.514-approximation. To the best of our knowledge, this is the first example where querying a submodular function on infeasible sets leads to provably better results. Through the link to the (non-streaming) robust setting mentioned previously, both of these algorithms improve on the current state of the art for robust submodular maximization, showing that approximation factors beyond 1\/2 are possible. Moreover, exploiting the link of our model to streaming, we settle the approximability for streaming algorithms by presenting a tight 1\/2+\u025b hardness result, based on the construction of a new family of coverage functions. This improves on a prior 0.586 hardness and matches, up to an arbitrarily small margin, the best-known approximation algorithm.<\/jats:p>","DOI":"10.1145\/3588564","type":"journal-article","created":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T12:08:38Z","timestamp":1682338118000},"page":"1-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1535-2979","authenticated-orcid":false,"given":"Moran","family":"Feldman","sequence":"first","affiliation":[{"name":"University of Haifa"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2336-9826","authenticated-orcid":false,"given":"Ashkan","family":"Norouzi-Fard","sequence":"additional","affiliation":[{"name":"Google Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2997-1372","authenticated-orcid":false,"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[{"name":"EPFL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7148-9304","authenticated-orcid":false,"given":"Rico","family":"Zenklusen","sequence":"additional","affiliation":[{"name":"ETH Zurich"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,8,12]]},"reference":[{"key":"e_1_3_3_2_2","article-title":"Submodular secretary problem with shortlists","volume":"1809","author":"Agrawal Shipra","year":"2018","unstructured":"Shipra Agrawal, Mohammad Shadravan, and Cliff Stein. 2018. Submodular secretary problem with shortlists. CoRR abs\/1809.05082 (2018). http:\/\/arxiv.org\/abs\/1809.05082.","journal-title":"CoRR"},{"key":"e_1_3_3_3_2","article-title":"Optimal streaming algorithms for submodular maximization with cardinality constraints","volume":"1911","author":"Alaluf Naor","year":"2020","unstructured":"Naor Alaluf, Alina Ene, Moran Feldman, Huy L. Nguyen, and Andrew Suh. 2020. Optimal streaming algorithms for submodular maximization with cardinality constraints. CoRR abs\/1911.12959 (2020). http:\/\/arxiv.org\/abs\/1911.12959.","journal-title":"CoRR"},{"key":"e_1_3_3_4_2","first-page":"118","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS\u201910)","volume":"23","author":"Bach Francis R.","year":"2010","unstructured":"Francis R. Bach. 2010. Structured sparsity-inducing norms through submodular functions. In Proceedings of Advances in Neural Information Processing Systems (NIPS\u201910), Vol. 23. 118\u2013126."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623637"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/P15-1054"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.19"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316304"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188752"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2002.1004344"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.74"},{"key":"e_1_3_3_12_2","first-page":"508","volume-title":"Proceedings of the 34th International Conference on Machine Learning (ICML\u201917)","author":"Bogunovic Ilija","year":"2017","unstructured":"Ilija Bogunovic, Slobodan Mitrovic, Jonathan Scarlett, and Volkan Cevher. 2017. Robust submodular maximization: A non-uniform partitioning approach. In Proceedings of the 34th International Conference on Machine Learning (ICML\u201917). 508\u2013516. http:\/\/proceedings.mlr.press\/v70\/bogunovic17a.html."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.80"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","unstructured":"A. Chakrabarti. 2007. Lower bounds for multi-player pointer jumping. In Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC\u201907) .","DOI":"10.1109\/CCC.2007.14"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07557-0_18"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.20"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316327"},{"key":"e_1_3_3_19_2","first-page":"Article 45, 14","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919)","author":"Cormode G.","year":"2019","unstructured":"G. Cormode, J. Dark, and C. Konrad. 2019. Independent sets in vertex-arrival streams. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP\u201919). Article 45, 14 pages."},{"key":"e_1_3_3_20_2","first-page":"1236","volume-title":"Proceedings of the 32nd International Conference on Machine Learning (ICML\u201915)","author":"Barbosa Rafael da Ponte","year":"2015","unstructured":"Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen, and Justin Ward. 2015. The power of randomization: Distributed submodular maximization on massive datasets. In Proceedings of the 32nd International Conference on Machine Learning (ICML\u201915). 1236\u20131244."},{"key":"e_1_3_3_21_2","first-page":"1592","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS\u201912)","volume":"25","author":"Das Abhimanyu","year":"2012","unstructured":"Abhimanyu Das, Anirban Dasgupta, and Ravi Kumar. 2012. Selecting diverse features via spectral regularization. In Proceedings of Advances in Neural Information Processing Systems (NIPS\u201912), Vol. 25. 1592\u20131600."},{"key":"e_1_3_3_22_2","first-page":"1057","volume-title":"Proceedings of the 28th International Conference on Machine Learning (ICML\u201911)","author":"Das Abhimanyu","year":"2011","unstructured":"Abhimanyu Das and David Kempe. 2011. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proceedings of the 28th International Conference on Machine Learning (ICML\u201911). 1057\u20131064."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.18"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316389"},{"key":"e_1_3_3_25_2","first-page":"1833","volume-title":"Proceedings of the 36th International Conference on Machine Learning (ICML\u201919)","author":"Fahrbach Matthew","year":"2019","unstructured":"Matthew Fahrbach, Vahab S. Mirrokni, and Morteza Zadimoghaddam. 2019. Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In Proceedings of the 36th International Conference on Machine Learning (ICML\u201919). 1833\u20131842."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.17"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"e_1_3_3_29_2","article-title":"Do less, get more: Streaming submodular maximization with subsampling","volume":"1802","author":"Feldman Moran","year":"2018","unstructured":"Moran Feldman, Amin Karbasi, and Ehsan Kazemi. 2018. Do less, get more: Streaming submodular maximization with subsampling. CoRR abs\/1802.07098 (2018).","journal-title":"CoRR"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.5555\/2208436.2208448"},{"key":"e_1_3_3_31_2","article-title":"Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model","volume":"2002","author":"Huang Chien-Chung","year":"2020","unstructured":"Chien-Chung Huang, Naonori Kakimura, Simon Mauras, and Yuichi Yoshida. 2020. Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model. CoRR abs\/2002.05477 (2020). https:\/\/arxiv.org\/abs\/2002.05477.","journal-title":"CoRR"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a006"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.121"},{"key":"e_1_3_3_34_2","first-page":"3311","volume-title":"Proceedings of the 36th International Conference on Machine Learning (ICML\u201919)","author":"Kazemi Ehsan","year":"2019","unstructured":"Ehsan Kazemi, Marko Mitrovic, Morteza Zadimoghaddam, Silvio Lattanzi, and Amin Karbasi. 2019. 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\u201919). 3311\u20133320. http:\/\/proceedings.mlr.press\/v97\/kazemi19a.html."},{"key":"e_1_3_3_35_2","first-page":"2544","volume-title":"Proceedings of the 35th International Conference on Machine Learning (ICML\u201918)","author":"Kazemi Ehsan","year":"2018","unstructured":"Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. 2018. Scalable deletion-robust submodular maximization: Data summarization with privacy and fairness constraints. In Proceedings of the 35th International Conference on Machine Learning (ICML\u201918). 2544\u20132553."},{"key":"e_1_3_3_36_2","unstructured":"Andreas Krause. n.d. Submodularity in Machine Learning. Retrieved April. 29 2023 from http:\/\/submodularity.org\/."},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.4230\/OASIcs.SOSA.2019.18"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-018-9878-x"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746624"},{"key":"e_1_3_3_40_2","first-page":"2449","volume-title":"Proceedings of the 34th International Conference on Machine Learning (ICML\u201917)","author":"Mirzasoleiman Baharan","year":"2017","unstructured":"Baharan Mirzasoleiman, Amin Karbasi, and Andreas Krause. 2017. Deletion-robust submodular maximization: Data summarization with \u201cthe Right to be Forgotten.\u201d In Proceedings of the 34th International Conference on Machine Learning (ICML\u201917). 2449\u20132458."},{"key":"e_1_3_3_41_2","first-page":"4560","volume-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS\u201917)","author":"Mitrovic Slobodan","year":"2017","unstructured":"Slobodan Mitrovic, Ilija Bogunovic, Ashkan Norouzi-Fard, Jakub Tarnawski, and Volkan Cevher. 2017. Streaming robust submodular maximization: A partitioned thresholding approach. In Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS\u201917). 4560\u20134569."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_3_3_44_2","first-page":"3826","volume-title":"Proceedings of the 35th International Conference on Machine Learning (ICML\u201918)","author":"Norouzi-Fard Ashkan","year":"2018","unstructured":"Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrovic, Amir Zandieh, Aidasadat Mousavifar, and Ola Svensson. 2018. Beyond 1\/2-approximation for submodular maximization on massive data streams. In Proceedings of the 35th International Conference on Machine Learning (ICML\u201918). 3826\u20133835. http:\/\/proceedings.mlr.press\/v80\/norouzi-fard18a.html."},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-33461-5_26"},{"key":"e_1_3_3_46_2","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver A.","year":"2003","unstructured":"A. Schrijver. 2003. Combinatorial Optimization: Polyhedra and Efficiency. Springer."},{"key":"e_1_3_3_47_2","first-page":"1341","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS\u201914)","volume":"27","author":"Zheng Jingjing","year":"2014","unstructured":"Jingjing Zheng, Zhuolin Jiang, Rama Chellappa, and P. Jonathon Phillips. 2014. Submodular attribute selection for action recognition in video. In Proceedings of Advances in Neural Information Processing Systems (NIPS\u201914), Vol. 27. 1341\u20131349."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588564","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588564","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:13Z","timestamp":1750178833000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588564"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,12]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8,31]]}},"alternative-id":["10.1145\/3588564"],"URL":"https:\/\/doi.org\/10.1145\/3588564","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,12]]},"assertion":[{"value":"2021-08-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-04","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-08-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}