{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T15:15:23Z","timestamp":1775229323460,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":67,"publisher":"ACM","funder":[{"name":"Israel Science Foundation","award":["459\\\/20, 3001\\\/24"],"award-info":[{"award-number":["459\\\/20, 3001\\\/24"]}]},{"name":"United States - Israel Binational Science Foundation","award":["2022418"],"award-info":[{"award-number":["2022418"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718120","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"1130-1141","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7014-8954","authenticated-orcid":false,"given":"Niv","family":"Buchbinder","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel-Aviv, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1535-2979","authenticated-orcid":false,"given":"Moran","family":"Feldman","sequence":"additional","affiliation":[{"name":"University of Haifa, Haifa, Israel"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00103-1"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2907052"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000039"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.110"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2001.10011"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1017\/S000497270004140X"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01570-6"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3184990"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/MOOR.2018.0955"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649630"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00050"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2409.14325"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M125515X"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.106"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382820"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.60"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839655"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2405.05202"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.IPL.2006.06.003"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90003-9"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.8.789"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70732-5"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.34"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.14"},{"key":"e_1_3_2_1_30_1","unstructured":"Moran Feldman. 2013. Maximization problems with submodular objective functions. Ph. D. Dissertation. Technion - Israel Institute of Technology Israel. https:\/\/technion.primo.exlibrisgroup.com\/permalink\/972TEC_INST\/q1jq5o\/alma990023478210203971"},{"key":"e_1_3_2_1_31_1","article-title":"How Do You Want Your Greedy: Simultaneous or Repeated","volume":"24","author":"Feldman Moran","year":"2023","unstructured":"Moran Feldman, Christopher Harshaw, and Amin Karbasi. 2023. How Do You Want Your Greedy: Simultaneous or Repeated? J. Mach. Learn. Res., 24 (2023), 72:1\u201372:87. http:\/\/jmlr.org\/papers\/v24\/21-0782.html","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.46"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23719-5_66"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/130920277"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109624"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523688"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_2_1_39_1","volume-title":"Symposium on Discrete Algorithms (SODA), S. Rao Kosaraju (Ed.). ACM\/SIAM","author":"Halperin Eran","year":"2001","unstructured":"Eran Halperin and Uri Zwick. 2001. Combinatorial approximation algorithms for the maximum directed cut problem. In Symposium on Discrete Algorithms (SODA), S. Rao Kosaraju (Ed.). ACM\/SIAM, Philadelphia, PA, USA. 1\u20137. http:\/\/dl.acm.org\/citation.cfm?id=365411.365412"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367524"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917662"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120891"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2011.5995589"},{"key":"e_1_3_2_1_45_1","first-page":"341","article-title":"The efficacy of the greedy algorithm","volume":"17","author":"Jenkyns T.","year":"1976","unstructured":"T. Jenkyns. 1976. The efficacy of the greedy algorithm. Cong. Num., 17 (1976), 341\u2013350.","journal-title":"Cong. Num."},{"key":"e_1_3_2_1_46_1","volume-title":"Complexity of Computer Computations","author":"Karp Richard M.","unstructured":"Richard M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (Eds.). Plenum Press, New York, NY. 85\u2013103."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.4086\/TOC.2015.V011A004"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2024.100"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70322-4"},{"key":"e_1_3_2_1_52_1","volume-title":"Near-optimal Nonmyopic Value of Information in Graphical Models. In Conference in Uncertainty in Artificial Intelligence (UAI). AUAI Press","author":"Krause Andreas","year":"2005","unstructured":"Andreas Krause and Carlos Guestrin. 2005. Near-optimal Nonmyopic Value of Information in Graphical Models. In Conference in Uncertainty in Artificial Intelligence (UAI). AUAI Press, Arlington, Virginia. 324\u2013331. https:\/\/dslpitt.org\/uai\/displayArticleDetails.jsp?mmnu=1&smnu=2&article_id=1238&proceeding_id=21"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1061\/(ASCE)0733-9496(2008)134:6(516)"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/1390681.1390689"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0592"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/090750020"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1287\/MOOR.1100.0463"},{"key":"e_1_3_2_1_58_1","volume-title":"Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics (HLT-NAACL). The Association for Computational Linguistics","author":"Lin Hui","unstructured":"Hui Lin and Jeff A. Bilmes. 2010. Multi-document Summarization via Budgeted Maximization of Submodular Functions. In Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics (HLT-NAACL). The Association for Computational Linguistics, Stroudsburg, PA. 912\u2013920. https:\/\/aclanthology.org\/N10-1134\/"},{"key":"e_1_3_2_1_59_1","volume-title":"Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL-HLT), Dekang Lin, Yuji Matsumoto, and Rada Mihalcea (Eds.). The Association for Computer Linguistics","author":"Lin Hui","unstructured":"Hui Lin and Jeff A. Bilmes. 2011. A Class of Submodular Functions for Document Summarization. In Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL-HLT), Dekang Lin, Yuji Matsumoto, and Rada Mihalcea (Eds.). The Association for Computer Linguistics, Stroudsburg, PA. 510\u2013520. https:\/\/aclanthology.org\/P11-1052\/"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1287\/MOOR.3.3.177"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.83"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2022.41"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.APPROX"},{"key":"e_1_3_2_1_65_1","volume-title":"Combinatorial Optimization: Polyhedra and Effciency","author":"Schrijver A.","year":"2003","unstructured":"A. Schrijver.. 2003. Combinatorial Optimization: Polyhedra and Effciency. Springer-Verlag, Berlin, Germany."},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797328847"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3718120","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:39:13Z","timestamp":1750693153000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718120"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":67,"alternative-id":["10.1145\/3717823.3718120","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718120","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"}}]}}