{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T16:43:11Z","timestamp":1770741791818,"version":"3.49.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T00:00:00Z","timestamp":1559865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["1585\/15 and 1336\/16"],"award-info":[{"award-number":["1585\/15 and 1336\/16"]}]},{"name":"USIsrael BSF","award":["2014414"],"award-info":[{"award-number":["2014414"]}]},{"name":"ERC","award":["335288"],"award-info":[{"award-number":["335288"]}]},{"name":"OptApprox and ISF","award":["1357\/16"],"award-info":[{"award-number":["1357\/16"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>Submodular function maximization has been studied extensively in recent years under various constraints and models. The problem plays a major role in various disciplines. We study a natural online variant of this problem in which elements arrive one by one and the algorithm has to maintain a solution obeying certain constraints at all times. Upon arrival of an element, the algorithm has to decide whether to accept the element into its solution and may preempt previously chosen elements. The goal is to maximize a submodular function over the set of elements in the solution.<\/jats:p>\n          <jats:p>\n            We study two special cases of this general problem and derive upper and lower bounds on the competitive ratio. Specifically, we design a 1\/\n            <jats:italic>e<\/jats:italic>\n            -competitive algorithm for the unconstrained case in which the algorithm may hold any subset of the elements, and constant competitive ratio algorithms for the case where the algorithm may hold at most\n            <jats:italic>k<\/jats:italic>\n            elements in its solution.\n          <\/jats:p>","DOI":"10.1145\/3309764","type":"journal-article","created":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T12:10:51Z","timestamp":1560168651000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Online Submodular Maximization with Preemption"],"prefix":"10.1145","volume":"15","author":[{"given":"Niv","family":"Buchbinder","sequence":"first","affiliation":[{"name":"Tel Aviv University, Israel, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1535-2979","authenticated-orcid":false,"given":"Moran","family":"Feldman","sequence":"additional","affiliation":[{"name":"The Open University of Israel, Raanana, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roy","family":"Schwartz","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Beating the logarithmic lower bound: Randomized preemptive disjoint paths and call control algorithms","author":"Adler Ran","unstructured":"Ran Adler and Yossi Azar . 1999. Beating the logarithmic lower bound: Randomized preemptive disjoint paths and call control algorithms . In SODA. Society for Industrial and Applied Mathematics , Philadelphia, PA , 1--10. Ran Adler and Yossi Azar. 1999. Beating the logarithmic lower bound: Randomized preemptive disjoint paths and call control algorithms. In SODA. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1--10."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00103-1"},{"key":"e_1_2_1_3_1","volume-title":"Submodular Max-SAT","author":"Azar Yossi","unstructured":"Yossi Azar , Iftah Gamzu , and Ran Roth . 2011. Submodular Max-SAT . In ESA. Springer-Verlag , Berlin , 323--334. Yossi Azar, Iftah Gamzu, and Ran Roth. 2011. Submodular Max-SAT. In ESA. Springer-Verlag, Berlin, 323--334."},{"key":"e_1_2_1_4_1","volume-title":"Workshop on Ad Auctions.","author":"Babaioff Moshe","unstructured":"Moshe Babaioff , Jason D. Hartline , and Robert D. Kleinberg . 2008. Online algorithms with buyback . In Workshop on Ad Auctions. Moshe Babaioff, Jason D. Hartline, and Robert D. Kleinberg. 2008. Online algorithms with buyback. In Workshop on Ad Auctions."},{"key":"e_1_2_1_5_1","volume-title":"Kleinberg","author":"Babaioff Moshe","year":"2009","unstructured":"Moshe Babaioff , Jason D. Hartline , and Robert D . Kleinberg . 2009 . Selling ad campaigns: Online algorithms with cancellations. In EC. ACM, New York , 61--70. Moshe Babaioff, Jason D. Hartline, and Robert D. Kleinberg. 2009. Selling ad campaigns: Online algorithms with cancellations. In EC. ACM, New York, 61--70."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-010-9318-6"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500121"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.73"},{"key":"e_1_2_1_9_1","volume-title":"Submodular maximization with cardinality constraints","author":"Buchbinder Niv","unstructured":"Niv Buchbinder , Moran Feldman , Joseph (Seffi) Naor , and Roy Schwartz . 2014. Submodular maximization with cardinality constraints . In SODA. Society for Industrial and Applied Mathematics , Philadelphia, PA , 1433--1452. Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, and Roy Schwartz. 2014. Submodular maximization with cardinality constraints. In SODA. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1433--1452."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0900-7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382820"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.06.003"},{"key":"e_1_2_1_14_1","volume-title":"An online mechanism for ad slot reservations with cancellations","author":"Constantin Florin","unstructured":"Florin Constantin , Jon Feldman , S. Muthukrishnan , and Martin P\u00e1l. 2009. An online mechanism for ad slot reservations with cancellations . In SODA. Society for Industrial and Applied Mathematics , Philadelphia, PA , 1265--1274. Florin Constantin, Jon Feldman, S. Muthukrishnan, and Martin P\u00e1l. 2009. An online mechanism for ad slot reservations with cancellations. In SODA. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1265--1274."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.8.789"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70732-5"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a005"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118767.3119112"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.12.002"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_21_1","volume-title":"Goemans","author":"Feige Uriel","year":"1995","unstructured":"Uriel Feige and Michel X . Goemans . 1995 . Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT. In ISTCS. IEEE Computer Society , Washington, DC, 182--189. Uriel Feige and Michel X. Goemans. 1995. Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT. In ISTCS. IEEE Computer Society, Washington, DC, 182--189."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9806-z"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.14"},{"key":"e_1_2_1_25_1","volume-title":"Improved competitive ratios for submodular secretary problems","author":"Feldman Moran","unstructured":"Moran Feldman , Joseph (Seffi) Naor , and Roy Schwartz . 2011. Improved competitive ratios for submodular secretary problems . In APPROX. Springer-Verlag , Berlin , 218--229. Moran Feldman, Joseph (Seffi) Naor, and Roy Schwartz. 2011. Improved competitive ratios for submodular secretary problems. In APPROX. Springer-Verlag, Berlin, 218--229."},{"key":"e_1_2_1_26_1","volume-title":"Nonmonotone submodular maximization via a structural continuous greedy algorithm","author":"Feldman Moran","unstructured":"Moran Feldman , Joseph (Seffi) Naor , and Roy Schwartz . 2011. Nonmonotone submodular maximization via a structural continuous greedy algorithm . In ICALP. Springer-Verlag , Berlin , 342--353. Moran Feldman, Joseph (Seffi) Naor, and Roy Schwartz. 2011. Nonmonotone submodular maximization via a structural continuous greedy algorithm. In ICALP. Springer-Verlag, Berlin, 342--353."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.46"},{"key":"e_1_2_1_28_1","volume-title":"Tight approximation algorithms for maximum general assignment problems","author":"Fleischer Lisa","unstructured":"Lisa Fleischer , Michel X. Goemans , Vahab S. Mirrokni , and Maxim Sviridenko . 2006. Tight approximation algorithms for maximum general assignment problems . In SODA. Society for Industrial and Applied Mathematics , Philadelphia, PA , 611--620. Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, and Maxim Sviridenko. 2006. Tight approximation algorithms for maximum general assignment problems. In SODA. Society for Industrial and Applied Mathematics, Philadelphia, PA, 611--620."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-013-0321-5"},{"key":"e_1_2_1_30_1","volume-title":"Submodular maximization by simulated annealing","author":"Gharan Shayan Oveis","unstructured":"Shayan Oveis Gharan and Jan Vondr\u00e1k . 2011. Submodular maximization by simulated annealing . In SODA. Society for Industrial and Applied Mathematics , Philadelphia, PA , 1098--1117. Shayan Oveis Gharan and Jan Vondr\u00e1k. 2011. Submodular maximization by simulated annealing. In SODA. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1098--1117."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_32_1","volume-title":"Constrained non-monotone submodular maximization: Offline and secretary algorithms","author":"Gupta Anupam","unstructured":"Anupam Gupta , Aaron Roth , Grant Schoenebeck , and Kunal Talwar . 2010. Constrained non-monotone submodular maximization: Offline and secretary algorithms . In WINE. Springer-Verlag , Berlin , 246--257. Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. 2010. Constrained non-monotone submodular maximization: Offline and secretary algorithms. In WINE. Springer-Verlag, Berlin, 246--257."},{"key":"e_1_2_1_33_1","volume-title":"Combinatorial approximation algorithms for the maximum directed cut problem","author":"Halperin Eran","unstructured":"Eran Halperin and Uri Zwick . 2001. Combinatorial approximation algorithms for the maximum directed cut problem . In SODA. Society for Industrial and Applied Mathematics , Philadelphia, PA , 1--7. Eran Halperin and Uri Zwick. 2001. Combinatorial approximation algorithms for the maximum directed cut problem. In SODA. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1--7."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9822-z"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_36_1","volume-title":"Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization","author":"Huang Norman","unstructured":"Norman Huang and Allan Borodin . 2014. Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization . In ISAAC. Springer , Cham , 528--539. Norman Huang and Allan Borodin. 2014. Bounds on double-sided myopic algorithms for unconstrained non-monotone submodular maximization. In ISAAC. Springer, Cham, 528--539."},{"key":"e_1_2_1_37_1","volume-title":"Removable online knapsack problems","author":"Iwama Kazuo","unstructured":"Kazuo Iwama and Shiro Taketomi . 2002. Removable online knapsack problems . In ICALP. Springer-Verlag , Berlin , 293--305. Kazuo Iwama and Shiro Taketomi. 2002. Removable online knapsack problems. In ICALP. Springer-Verlag, Berlin, 293--305."},{"key":"e_1_2_1_38_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 , 85--103. 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, 85--103."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_2_1_40_1","volume-title":"Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9 (January","author":"Krause Andreas","year":"2008","unstructured":"Andreas Krause , Ajit Singh , and Carlos Guestrin . 2008. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9 (January 2008 ), 235--284. Andreas Krause, Ajit Singh, and Carlos Guestrin. 2008. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9 (January 2008), 235--284."},{"key":"e_1_2_1_41_1","volume-title":"Near-optimal nonmyopic value of information in graphical models","author":"Krause Andreas","unstructured":"Andreas Krause and Carlos Guestrin . 2005. Near-optimal nonmyopic value of information in graphical models . In UAI. AUAI Press , Arlington, VA , 5. Andreas Krause and Carlos Guestrin. 2005. Near-optimal nonmyopic value of information in graphical models. In UAI. AUAI Press, Arlington, VA, 5."},{"key":"e_1_2_1_42_1","volume-title":"Near-optimal observation selection using submodular functions","author":"Krause Andreas","unstructured":"Andreas Krause and Carlos Guestrin . 2007. Near-optimal observation selection using submodular functions . In AAAI. AAAI Press , Palo Alto, CA , 1650--1654. Andreas Krause and Carlos Guestrin. 2007. Near-optimal observation selection using submodular functions. In AAAI. AAAI Press, Palo Alto, CA, 1650--1654."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1061\/(ASCE)0733-9496(2008)134:6(516)"},{"key":"e_1_2_1_44_1","volume-title":"Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems","author":"Lewin Michael","unstructured":"Michael Lewin , Dror Livnat , and Uri Zwick . 2002. Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems . In IPCO. Springer-Verlag , Berlin , 67--82. Michael Lewin, Dror Livnat, and Uri Zwick. 2002. Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems. In IPCO. Springer-Verlag, Berlin, 67--82."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1857999.1858133"},{"key":"e_1_2_1_46_1","volume-title":"A class of submodular functions for document summarization","author":"Lin Hui","unstructured":"Hui Lin and Jeff Bilmes . 2011. A class of submodular functions for document summarization . In HLT. Association for Computational Linguistics , Stroudsburg, PA , 510--520. Hui Lin and Jeff Bilmes. 2011. A class of submodular functions for document summarization. In HLT. Association for Computational Linguistics, Stroudsburg, PA, 510--520."},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Shiro Matuura and Tomomi Matsui. 2001. 0.863-approximation algorithm for MAX DICUT. In APPROX. Springer-Verlag Berlin 138--146.  Shiro Matuura and Tomomi Matsui. 2001. 0.863-approximation algorithm for MAX DICUT. In APPROX. Springer-Verlag Berlin 138--146.","DOI":"10.1007\/3-540-44666-4_17"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.53"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2013.02.002"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797328847"},{"key":"e_1_2_1_53_1","series-title":"Lecture Notes in Computer Science","volume-title":"Buyback problem - Approximate matroid intersection with cancellation costs","author":"Varadaraja Ashwinkumar Badanidiyuru","unstructured":"Ashwinkumar Badanidiyuru Varadaraja . 2011. Buyback problem - Approximate matroid intersection with cancellation costs . In Automata, Languages and Programming, Luca Aceto, Monika Henzinger, and Ji\u0159\u00ed Sgall (Eds.). Lecture Notes in Computer Science , Vol. 6755 . Springer-Verlag , Berlin , 379--390. Ashwinkumar Badanidiyuru Varadaraja. 2011. Buyback problem - Approximate matroid intersection with cancellation costs. In Automata, Languages and Programming, Luca Aceto, Monika Henzinger, and Ji\u0159\u00ed Sgall (Eds.). Lecture Notes in Computer Science, Vol. 6755. Springer-Verlag, Berlin, 379--390."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_52"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/110832318"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309764","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3309764","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:36Z","timestamp":1750204416000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3309764"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,7]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3309764"],"URL":"https:\/\/doi.org\/10.1145\/3309764","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,7]]},"assertion":[{"value":"2015-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}