{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:33Z","timestamp":1781028273276,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":66,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["852870"],"award-info":[{"award-number":["852870"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2504994"],"award-info":[{"award-number":["2504994"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2106444"],"award-info":[{"award-number":["2106444"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800918","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"2152-2163","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Poisson Process for Submodular Maximization"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-4801-1492","authenticated-orcid":false,"given":"Amit","family":"Ganz Rozenman","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0533-3926","authenticated-orcid":false,"given":"Ariel","family":"Kulik","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer-Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-3423-721X","authenticated-orcid":false,"given":"Roy","family":"Schwartz","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0827-233X","authenticated-orcid":false,"given":"Mohit","family":"Singh","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038913.96607.c2"},{"key":"e_1_3_2_1_2_1","volume-title":"Learning with Submodular Functions: A Convex Optimization Perspective","author":"Bach Francis","year":"1987","unstructured":"Francis Bach. 2013. Learning with Submodular Functions: A Convex Optimization Perspective. Now Publishers Inc., Hanover, MA, USA. isbn:1601987560"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.110"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539292"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1017\/S000497270004140X"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2018.0955"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649630"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00050"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718120"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.106"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0809"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958038"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/WACV.2015.99"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993740"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649730"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.06.003"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109675"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.34"},{"key":"e_1_3_2_1_21_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Ene Alina","year":"2019","unstructured":"Alina Ene and Huy L Nguyen. 2019. A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). 53\u20131."},{"key":"e_1_3_2_1_22_1","unstructured":"Alina Ene and Huy L Nguyen. 2019. Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint. In International Colloquium on Automata Languages and Programming. 132."},{"key":"e_1_3_2_1_23_1","article-title":"Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems","volume":"7","author":"Even-Dar Eyal","year":"2006","unstructured":"Eyal Even-Dar, Shie Mannor, and Yishay Mansour. 2006. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems.. Journal of machine learning research, 7, 6 (2006).","journal-title":"Journal of machine learning research"},{"key":"e_1_3_2_1_24_1","volume-title":"29th Annual European Symposium on Algorithms, ESA","author":"Fairstein Yaron","year":"2021","unstructured":"Yaron Fairstein, Ariel Kulik, and Hadas Shachnai. 2021. Modular and submodular optimization with multiple knapsack constraints via fractional grouping. In 29th Annual European Symposium on Algorithms, ESA 2021. 41."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132523"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.14"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a011"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.46"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2015.315"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/130920277"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109624"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.83"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367524"},{"key":"e_1_3_2_1_37_1","unstructured":"Monika Henzinger Paul Liu Jan Vondr\u00e1k and Da Wei Zheng. 2023. Faster submodular maximization for several classes of matroids. arXiv preprint arXiv:2305.00122."},{"key":"e_1_3_2_1_38_1","volume-title":"Gurumoorthy","author":"Jawanpuria Pratik","year":"2024","unstructured":"Pratik Jawanpuria, Bamdev Mishra, and Karthik S. Gurumoorthy. 2024. Revisiting stochastic submodular maximization with cardinality constraint: A bandit perspective. Transactions on Machine Learning Research, issn:2835-8856 https:\/\/openreview.net\/forum?id=57ETChLAOE"},{"key":"e_1_3_2_1_39_1","volume-title":"Optimization of Complex Systems: Theory","author":"Ji Sai","year":"1803","unstructured":"Sai Ji, Dachuan Xu, Min Li, Yishui Wang, and Dongmei Zhang. 2020. Stochastic Greedy Algorithm Is Still Good: Maximizing Submodular + Supermodular Functions. In Optimization of Complex Systems: Theory, Models, Algorithms and Applications, Hoai An Le Thi, Hoai Minh Le, and Tao Pham Dinh (Eds.). Springer International Publishing, Cham. 488\u2013497. isbn:978-3-030-21803-4"},{"key":"e_1_3_2_1_40_1","volume-title":"Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS\u201917)","author":"Karimi Mohammad Reza","year":"2017","unstructured":"Mohammad Reza Karimi, Mario Lucic, Hamed Hassani, and Andreas Krause. 2017. Stochastic submodular maximization: the case of coverage functions. In Proceedings of the 31st International Conference on Neural Information Processing Systems (NIPS\u201917). Curran Associates Inc., Red Hook, NY, USA. 6856\u20136866. isbn:9781510860964"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_3_2_1_42_1","volume-title":"Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, Aarti Singh and Jerry Zhu (Eds.) (Proceedings of Machine Learning Research","volume":"1568","author":"Khanna Rajiv","year":"2017","unstructured":"Rajiv Khanna, Ethan Elenberg, Alex Dimakis, Sahand Negahban, and Joydeep Ghosh. 2017. Scalable Greedy Feature Selection via Weak Submodularity. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, Aarti Singh and Jerry Zhu (Eds.) (Proceedings of Machine Learning Research, Vol. 54). PMLR, 1560\u20131568. https:\/\/proceedings.mlr.press\/v54\/khanna17b.html"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118759.3119047"},{"key":"e_1_3_2_1_44_1","volume-title":"51st International Colloquium on Automata, Languages, and Programming (ICALP","author":"Kobayashi Yusuke","year":"2024","unstructured":"Yusuke Kobayashi and Tatsuya Terao. 2024. Subquadratic Submodular Maximization with a General Matroid Constraint. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). 100\u20131."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1061\/(ASCE)0733-9496(2008)134:6(516)"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/1390681.1390689"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0592"},{"key":"e_1_3_2_1_48_1","unstructured":"Vangipuram Lakshmikantham and Srinivasa Leela. 1969. Differential and integral inequalities: theory and applications: volume I: ordinary differential equations. Academic press."},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/090750020"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0463"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/501158.501161"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/1857999.1858133"},{"key":"e_1_3_2_1_53_1","volume-title":"Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies","author":"Lin Hui","unstructured":"Hui Lin and Jeff Bilmes. 2011. A Class of Submodular Functions for Document Summarization. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Dekang Lin, Yuji Matsumoto, and Rada Mihalcea (Eds.). Association for Computational Linguistics, Portland, Oregon, USA. 510\u2013520. https:\/\/aclanthology.org\/P11-1052\/"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2013.6639057"},{"key":"e_1_3_2_1_55_1","volume-title":"Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence (UAI\u201916)","author":"Malioutov Dmitry","unstructured":"Dmitry Malioutov, Abhishek Kumar, and Ian E.H. Yen. 2016. Large-scale submodular greedy exemplar selection with structured similarity matrices. In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence (UAI\u201916). AUAI Press, Arlington, Virginia, USA. 507\u2013516. isbn:9780996643115"},{"key":"e_1_3_2_1_56_1","volume-title":"International Conference on Machine Learning. 1358\u20131367","author":"Mirzasoleiman Baharan","year":"2016","unstructured":"Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. 2016. Fast constrained submodular maximization: Personalized data summarization. In International Conference on Machine Learning. 1358\u20131367."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9486"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/080714452"},{"key":"e_1_3_2_1_59_1","volume-title":"Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, 3, 3","author":"Nemhauser George L","year":"1978","unstructured":"George L Nemhauser and Laurence A Wolsey. 1978. Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations research, 3, 3 (1978), 177\u2013188."},{"key":"e_1_3_2_1_60_1","volume-title":"An analysis of approximations for maximizing submodular set functions\u2014I. Mathematical programming, 14","author":"Nemhauser George L","year":"1978","unstructured":"George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. 1978. An analysis of approximations for maximizing submodular set functions\u2014I. Mathematical programming, 14 (1978), 265\u2013294."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-023-01183-3"},{"key":"e_1_3_2_1_62_1","volume-title":"Introduction to Probability Models","author":"Ross Sheldon M.","unstructured":"Sheldon M. Ross. 2014. Introduction to Probability Models (11th ed.). Academic Press. isbn:9780124079489","edition":"11"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623674"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623331"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1137\/110832318"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800918","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800918","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:55:33Z","timestamp":1781027733000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800918"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":66,"alternative-id":["10.1145\/3798129.3800918","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800918","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}