{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:35:45Z","timestamp":1767339345950,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":64,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"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":"publisher","award":["1357\/16"],"award-info":[{"award-number":["1357\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316327","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"102-113","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Unconstrained submodular maximization with constant adaptive complexity"],"prefix":"10.1145","author":[{"given":"Lin","family":"Chen","sequence":"first","affiliation":[{"name":"Yale University, USA"}]},{"given":"Moran","family":"Feldman","sequence":"additional","affiliation":[{"name":"Open University of Israel, Israel"}]},{"given":"Amin","family":"Karbasi","sequence":"additional","affiliation":[{"name":"Yale University, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634184"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623637"},{"key":"e_1_3_2_1_3_1","unstructured":"Eric Balkanski Aviad Rubinstein and Yaron Singer. 2019.  Eric Balkanski Aviad Rubinstein and Yaron Singer. 2019."},{"volume-title":"STOC","author":"Balkanski Eric","key":"e_1_3_2_1_4_1"},{"key":"e_1_3_2_1_5_1","unstructured":"STOC \u201919 June 23\u201326 2019 Phoenix AZ USA Lin Chen Moran Feldman and Amin Karbasi  STOC \u201919 June 23\u201326 2019 Phoenix AZ USA Lin Chen Moran Feldman and Amin Karbasi"},{"volume-title":"International Conference on Machine Learning. JMLR.org, 1236\u20131244","year":"2015","author":"Barbosa Rafael","key":"e_1_3_2_1_6_1"},{"volume-title":"Foundations of Computer Science (FOCS)","author":"da Ponte Barbosa Rafael","key":"e_1_3_2_1_7_1"},{"key":"e_1_3_2_1_8_1","unstructured":"An Bian Joachim M Buhmann and Andreas Krause. 2018.  An Bian Joachim M Buhmann and Andreas Krause. 2018."},{"key":"e_1_3_2_1_9_1","unstructured":"Optimal DRSubmodular Maximization and Applications to Provable Mean Field Inference. arXiv preprint arXiv:1805.07482 (2018).  Optimal DRSubmodular Maximization and Applications to Provable Mean Field Inference. arXiv preprint arXiv:1805.07482 (2018)."},{"volume-title":"Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS). JMLR.org, 111\u2013120","year":"2017","author":"Bian Andrew An","key":"e_1_3_2_1_10_1"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3184990"},{"key":"e_1_3_2_1_12_1","unstructured":"Niv Buchbinder Moran Feldman Joseph Naor and Roy Schwartz. 2014.  Niv Buchbinder Moran Feldman Joseph Naor and Roy Schwartz. 2014."},{"volume-title":"Maximization with Cardinality Constraints. In ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics","author":"Submodular","key":"e_1_3_2_1_13_1"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"e_1_3_2_1_15_1","unstructured":"Niv Buchbinder Moran Feldman and Roy Schwartz. 2015.  Niv Buchbinder Moran Feldman and Roy Schwartz. 2015."},{"volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, Society for Industrial and Applied Mathematics","author":"Online","key":"e_1_3_2_1_16_1"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_3_2_1_18_1","unstructured":"Chandra Chekuri Shalmoli Gupta and Kent Quanrud. 2015.  Chandra Chekuri Shalmoli Gupta and Kent Quanrud. 2015."},{"volume-title":"International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Submodular Function Maximization Streaming Algorithms","key":"e_1_3_2_1_19_1"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.20"},{"key":"e_1_3_2_1_21_1","unstructured":"Lin Chen Moran Feldman and Amin Karbasi. 2018. Unconstrained Submodular Maximization with Constant Adaptive Complexity. CoRR abs\/1811.06603 (2018).  Lin Chen Moran Feldman and Amin Karbasi. 2018. Unconstrained Submodular Maximization with Constant Adaptive Complexity. CoRR abs\/1811.06603 (2018)."},{"key":"e_1_3_2_1_22_1","unstructured":"arXiv: 1811.06603 http:\/\/arxiv.org\/abs\/1811.06603  arXiv: 1811.06603 http:\/\/arxiv.org\/abs\/1811.06603"},{"volume-title":"Sparse Approximation and Dictionary Selection. In International Conference on Machine Learning. JMLR.org, 1057\u20131064","year":"2011","author":"Das Abhimanyu","key":"e_1_3_2_1_23_1"},{"volume-title":"Advances in Neural Information Processing Systems","author":"Dolhansky Brian W","key":"e_1_3_2_1_24_1"},{"key":"e_1_3_2_1_25_1","unstructured":"Ethan R. Elenberg Alexandros G. Dimakis Moran Feldman and Amin Karbasi. 2017.  Ethan R. Elenberg Alexandros G. Dimakis Moran Feldman and Amin Karbasi. 2017."},{"volume-title":"Advances in Neural Information Processing Systems","author":"Submodularity Streaming Weak","key":"e_1_3_2_1_26_1"},{"key":"e_1_3_2_1_27_1","unstructured":"Ethan R. Elenberg Rajiv Khanna Alexandros G. Dimakis and Sahand Negahban. 2016.  Ethan R. Elenberg Rajiv Khanna Alexandros G. Dimakis and Sahand Negahban. 2016."},{"key":"e_1_3_2_1_28_1","unstructured":"Restricted Strong Convexity Implies Weak Submodularity. CoRR abs\/1612.00804 (2016).  Restricted Strong Convexity Implies Weak Submodularity. CoRR abs\/1612.00804 (2016)."},{"key":"e_1_3_2_1_29_1","unstructured":"Alina Ene and Huy L. Nguyen. 2019.  Alina Ene and Huy L. Nguyen. 2019."},{"volume-title":"STOC. ACM","author":"Ene Alina","key":"e_1_3_2_1_30_1"},{"key":"e_1_3_2_1_31_1","unstructured":"Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam. 2018.  Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam. 2018."},{"key":"e_1_3_2_1_32_1","unstructured":"Non-monotone Submodular Maximization with Nearly Optimal Adaptivity Complexity. CoRR abs\/1808.06932 (2018).  Non-monotone Submodular Maximization with Nearly Optimal Adaptivity Complexity. CoRR abs\/1808.06932 (2018)."},{"key":"e_1_3_2_1_33_1","unstructured":"Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam. 2019.  Matthew Fahrbach Vahab S. Mirrokni and Morteza Zadimoghaddam. 2019."},{"key":"e_1_3_2_1_34_1","unstructured":"Uriel Feige Vahab S. Mirrokni and Jan Vondr\u00e1k. 2011.  Uriel Feige Vahab S. Mirrokni and Jan Vondr\u00e1k. 2011."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"volume-title":"Conference on Learning Theory. JMLR.org, 758\u2013784","year":"2017","author":"Feldman Moran","key":"e_1_3_2_1_36_1"},{"key":"e_1_3_2_1_37_1","unstructured":"Moran Feldman Amin Karbasi and Ehsan Kazemi. 2018.  Moran Feldman Amin Karbasi and Ehsan Kazemi. 2018."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Moran Feldman Joseph Naor and Roy Schwartz. 2011. Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm - (Extended Abstract). In ICALP. Springer-Verlag Berlin Heidelberg 342\u2013353.   Moran Feldman Joseph Naor and Roy Schwartz. 2011. Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm - (Extended Abstract). In ICALP. Springer-Verlag Berlin Heidelberg 342\u2013353.","DOI":"10.1007\/978-3-642-22006-7_29"},{"key":"e_1_3_2_1_39_1","unstructured":"Moran Feldman Joseph Naor and Roy Schwartz. 2011.  Moran Feldman Joseph Naor and Roy Schwartz. 2011."},{"volume-title":"Foundations of Computer Science (FOCS)","author":"A","key":"e_1_3_2_1_40_1"},{"key":"e_1_3_2_1_41_1","unstructured":"Shayan Oveis Gharan and Jan Vondr\u00e1k. 2011.  Shayan Oveis Gharan and Jan Vondr\u00e1k. 2011."},{"volume-title":"SODA","author":"Simulated Annealing Submodular Maximization","key":"e_1_3_2_1_42_1"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/2208436.2208448"},{"key":"e_1_3_2_1_44_1","unstructured":"Andrew Guillory and Jeff A. Bilmes. 2011.  Andrew Guillory and Jeff A. Bilmes. 2011."},{"volume-title":"Uncertainty in Artificial Intelligence (UAI)","author":"Semi-Supervised Active","key":"e_1_3_2_1_45_1"},{"volume-title":"Advances in Neural Information Processing Systems","author":"Hassani S. Hamed","key":"e_1_3_2_1_46_1"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_3_2_1_48_1","unstructured":"Andreas Krause Carlos Guestrin Anupam Gupta and Jon M. Kleinberg. 2006.  Andreas Krause Carlos Guestrin Anupam Gupta and Jon M. Kleinberg. 2006."},{"key":"e_1_3_2_1_49_1","unstructured":"Ravi Kumar Benjamin Moseley Sergei Vassilvitskii and Andrea Vattani. 2013.  Ravi Kumar Benjamin Moseley Sergei Vassilvitskii and Andrea Vattani. 2013."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486168"},{"key":"e_1_3_2_1_51_1","unstructured":"Hui Lin and Jeff A. Bilmes. 2012.  Hui Lin and Jeff A. Bilmes. 2012."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746624"},{"volume-title":"AAAI Conference on Artificial Intelligence. AAAI Press","year":"2015","author":"Mirzasoleiman Baharan","key":"e_1_3_2_1_53_1"},{"key":"e_1_3_2_1_54_1","unstructured":"Baharan Mirzasoleiman Amin Karbasi Rik Sarkar and Andreas Krause. 2013.  Baharan Mirzasoleiman Amin Karbasi Rik Sarkar and Andreas Krause. 2013."},{"volume-title":"Advances in Neural Information Processing Systems","year":"2049","author":"Maximization Distributed Submodular","key":"e_1_3_2_1_55_1"},{"key":"e_1_3_2_1_56_1","unstructured":"Aryan Mokhtari Hamed Hassani and Amin Karbasi. 2018.  Aryan Mokhtari Hamed Hassani and Amin Karbasi. 2018."},{"volume-title":"Gradient Method for Stochastic Submodular Maximization: Closing the Gap. In International Conference on Artificial Intelligence and Statistics (AISTATS). PMLR","author":"Conditional","key":"e_1_3_2_1_57_1"},{"volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm\u00e4ssan","year":"2018","author":"Mokhtari Aryan","key":"e_1_3_2_1_58_1"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_3_2_1_61_1","unstructured":"Rad Niazadeh Tim Roughgarden and Joshua R. Wang. 2018. Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems (NeurIPS). Neural Information Processing Systems Foundation 9617\u20139627.   Rad Niazadeh Tim Roughgarden and Joshua R. Wang. 2018. Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems (NeurIPS). Neural Information Processing Systems Foundation 9617\u20139627."},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66182-7_55"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/110832318"},{"volume-title":"Proceedings of Annual Meeting of the Association for Computational Linguistics: Human Language Technologies. Association for Computational Linguistics","year":"2013","author":"Wei Kai","key":"e_1_3_2_1_64_1"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316327","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316327","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:01Z","timestamp":1750204441000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":64,"alternative-id":["10.1145\/3313276.3316327","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316327","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}