{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:03Z","timestamp":1750695003831,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":23,"publisher":"ACM","funder":[{"name":"Ministero dell'Universit\u00e0 e della Ricerca","award":["PRIN grant 2022EKNE5K ?Learning in Markets and Society?"],"award-info":[{"award-number":["PRIN grant 2022EKNE5K ?Learning in Markets and Society?"]}]},{"name":"Ministero dell'Universit\u00e0 e della Ricerca","award":["FAIR (Future Artificial Intelligence Research) project PE0000013, spoke 5"],"award-info":[{"award-number":["FAIR (Future Artificial Intelligence Research) project PE0000013, spoke 5"]}]},{"name":"Ministero dell'Universit\u00e0 e della Ricerca","award":["PNRR Project: SoBigData.it"],"award-info":[{"award-number":["PNRR Project: SoBigData.it"]}]},{"name":"Swiss State Secretariat for Education, Research and Innovation (SERI)","award":["contract number MB22.00054"],"award-info":[{"award-number":["contract number MB22.00054"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718131","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"1406-1417","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Cost of Consistency: Submodular Maximization with Constant Recourse"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0635-6812","authenticated-orcid":false,"given":"Paul","family":"D\u00fctting","sequence":"first","affiliation":[{"name":"Google Research, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6250-945X","authenticated-orcid":false,"given":"Federico","family":"Fusco","sequence":"additional","affiliation":[{"name":"Sapienza University of Rome, Rome, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3502-7559","authenticated-orcid":false,"given":"Silvio","family":"Lattanzi","sequence":"additional","affiliation":[{"name":"Google Research, Barcelona, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2336-9826","authenticated-orcid":false,"given":"Ashkan","family":"Norouzi-Fard","sequence":"additional","affiliation":[{"name":"Google Research, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2997-1372","authenticated-orcid":false,"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[{"name":"EPFL, Lausanne, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0717-1120","authenticated-orcid":false,"given":"Morteza","family":"Zadimoghaddam","sequence":"additional","affiliation":[{"name":"Google Research, Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"volume-title":"Dynamic Algorithms for Matroid Submodular Maximization","author":"Banihashem Kiarash","key":"e_1_3_2_1_1_1","unstructured":"Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, and Morteza Monemizadeh. 2024. Dynamic Algorithms for Matroid Submodular Maximization. In SODA. SIAM, 3485\u20133533."},{"volume-title":"Fully Dynamic k-Clustering with Fast Update Time and Small Recourse","author":"Bhattacharya Sayan","key":"e_1_3_2_1_2_1","unstructured":"Sayan Bhattacharya, Mart\u00edn Costa, Naveen Garg, Silvio Lattanzi, and Nikos Parotsidis. 2024. Fully Dynamic k-Clustering with Fast Update Time and Small Recourse. In FOCS. IEEE, 216\u2013227."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3184990"},{"volume-title":"Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint","author":"Buchbinder Niv","key":"e_1_3_2_1_4_1","unstructured":"Niv Buchbinder and Moran Feldman. 2024. Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint. In FOCS. IEEE, 700\u2013712."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3309764"},{"volume-title":"IPCO. 8494","author":"Chakrabarti Amit","key":"e_1_3_2_1_6_1","unstructured":"Amit Chakrabarti and Sagar Kale. 2014. Submodular Maximization Meets Streaming: Matchings, Matroids, and More. In IPCO. 8494, Springer, 210\u2013221."},{"key":"e_1_3_2_1_7_1","article-title":"Online Submodular Maximization with Free Disposal","volume":"14","author":"Hubert Chan T.-H.","year":"2018","unstructured":"T.-H. Hubert Chan, Zhiyi Huang, Shaofeng H.-C. Jiang, Ning Kang, and Zhihao Gavin Tang. 2018. Online Submodular Maximization with Free Disposal. ACM Trans. Algorithms, 14, 4 (2018), 56:1\u201356:29.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Xi Chen and Binghui Peng. 2022. On the complexity of dynamic submodular maximization. In STOC. ACM 1685\u20131698.","DOI":"10.1145\/3519935.3519951"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_3_2_1_10_1","volume-title":"The Cost of Consistency: Submodular Maximization with Constant Recourse. arXiv, abs\/2412.02492","author":"D\u00fctting Paul","year":"2024","unstructured":"Paul D\u00fctting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard, Ola Svensson, and Morteza Zadimoghaddam. 2024. The Cost of Consistency: Submodular Maximization with Constant Recourse. arXiv, abs\/2412.02492 (2024)."},{"key":"e_1_3_2_1_11_1","unstructured":"Paul D\u00fctting Federico Fusco Silvio Lattanzi Ashkan Norouzi-Fard and Morteza Zadimoghaddam. 2024. Consistent Submodular Maximization. In ICML."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588564"},{"volume-title":"Consistent k-Clustering for General Metrics","author":"Fichtenberger Hendrik","key":"e_1_3_2_1_15_1","unstructured":"Hendrik Fichtenberger, Silvio Lattanzi, Ashkan Norouzi-Fard, and Ola Svensson. 2021. Consistent k-Clustering for General Metrics. In SODA. SIAM, 2660\u20132678."},{"volume-title":"Online Discrepancy with Recourse for Vectors and Graphs","author":"Gupta Anupam","key":"e_1_3_2_1_16_1","unstructured":"Anupam Gupta, Vijaykrishna Gurunathan, Ravishankar Krishnaswamy, Amit Kumar, and Sahil Singla. 2022. Online Discrepancy with Recourse for Vectors and Graphs. In SODA. SIAM, 1356\u20131383."},{"volume-title":"Fully-Dynamic Submodular Cover with Bounded Recourse","author":"Gupta Anupam","key":"e_1_3_2_1_17_1","unstructured":"Anupam Gupta and Roie Levin. 2020. Fully-Dynamic Submodular Cover with Bounded Recourse. In FOCS. IEEE, 1147\u20131157."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Russell Impagliazzo and Avi Wigderson. 1997. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In STOC. ACM 220\u2013229.","DOI":"10.1145\/258533.258590"},{"key":"e_1_3_2_1_19_1","unstructured":"Silvio Lattanzi Slobodan Mitrovic Ashkan Norouzi-Fard Jakub Tarnawski and Morteza Zadimoghaddam. 2020. Fully Dynamic Algorithm for Constrained Submodular Optimization. In NeurIPS."},{"key":"e_1_3_2_1_20_1","unstructured":"Silvio Lattanzi and Sergei Vassilvitskii. 2017. Consistent k-Clustering. In ICML. 1975\u20131984."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/110832318"},{"volume-title":"Fully Dynamic Consistent k-Center Clustering","author":"\u0141acki Jakub","key":"e_1_3_2_1_23_1","unstructured":"Jakub \u0141acki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram, and V\u00e1clav Rozho\u0148. 2024. Fully Dynamic Consistent k-Center Clustering. In SODA. SIAM, 3463\u20133484."}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718131","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:39:42Z","timestamp":1750693182000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":23,"alternative-id":["10.1145\/3717823.3718131","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718131","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}