{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,15]],"date-time":"2026-08-15T10:59:19Z","timestamp":1786791559287,"version":"build-2736575974"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,9,17]],"date-time":"2018-09-17T00:00:00Z","timestamp":1537142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong RGC","award":["17202715 and 17202115"],"award-info":[{"award-number":["17202715 and 17202115"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,10,31]]},"abstract":"<jats:p>We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in rounds, and the algorithm maintains a feasible set that is independent in the underlying matroid. In each round when a new element arrives, the algorithm may accept the new element into its feasible set and possibly remove elements from it, provided that the resulting set is still independent. The goal is to maximize the value of the final feasible set under some monotone submodular function, to which the algorithm has oracle access.<\/jats:p>\n          <jats:p>\n            For\n            <jats:italic>k<\/jats:italic>\n            -uniform matroids, we give a deterministic algorithm with competitive ratio at least 0.2959, and the ratio approaches 1\/\u03b1\n            <jats:sub>\u221e<\/jats:sub>\n            \u2248 0.3178 as\n            <jats:italic>k<\/jats:italic>\n            approaches infinity, improving the previous best ratio of 0.25 by Chakrabarti and Kale (IPCO 2014), Buchbinder et al. (SODA 2015), and Chekuri et al. (ICALP 2015). We also show that our algorithm is optimal among a class of deterministic monotone algorithms that accept a new arriving element only if the objective is strictly increased.\n          <\/jats:p>\n          <jats:p>\n            Further, we prove that no deterministic monotone algorithm can be strictly better than 0.25-competitive even for partition matroids, the most modest generalization of\n            <jats:italic>k<\/jats:italic>\n            -uniform matroids, matching the competitive ratio by Chakrabarti and Kale (IPCO 2014) and Chekuri et al. (ICALP 2015). Interestingly, we show that randomized algorithms are strictly more powerful by giving a (non-monotone) randomized algorithm for partition matroids with ratio 1\/\u03b1\n            <jats:sub>\u221e<\/jats:sub>\n            \u2248 0.3178.\n          <\/jats:p>","DOI":"10.1145\/3242770","type":"journal-article","created":{"date-parts":[[2018,9,17]],"date-time":"2018-09-17T12:14:54Z","timestamp":1537186494000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Online Submodular Maximization with Free Disposal"],"prefix":"10.1145","volume":"14","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[{"name":"The University of Hong Kong, Pokfulam Road, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9046-5236","authenticated-orcid":false,"given":"Zhiyi","family":"Huang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Pokfulam Road, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shaofeng H.-C.","family":"Jiang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Pokfulam Road, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ning","family":"Kang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Pokfulam Road, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhihao Gavin","family":"Tang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Pokfulam Road, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,9,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038913.96607.c2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_52"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 4th Workshop on Ad Auctions.","author":"Babaioff Moshe","year":"2008","unstructured":"Moshe Babaioff, Jason Hartline, and Robert Kleinberg. 2008. Selling banner ads: Online algorithms with buyback. In Proceedings of the 4th Workshop on Ad Auctions."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566383"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500121"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884464"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722209"},{"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.1007\/978-3-662-47672-7_26"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27821-4_7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496907"},{"key":"e_1_2_1_15_1","volume-title":"Martial Hebert, and J. Andrew Bagnell.","author":"Dey Debadeepta","year":"2012","unstructured":"Debadeepta Dey, Tian Yu Liu, Martial Hebert, and J. Andrew Bagnell. 2012. Contextual sequence prediction with application to control library optimization. Robotics: Science and Systems VIII. University of Sydney, Sydney, NSW, Australia. http:\/\/www.roboticsproceedings.org\/rss08\/p07.html."},{"key":"e_1_2_1_16_1","volume-title":"On the hardness of welfare maximization in combinatorial auctions with submodular valuations. CoRR abs\/1202.2792","author":"Dobzinski Shahar","year":"2012","unstructured":"Shahar Dobzinski and Jan Vondr\u00e1k. 2012. On the hardness of welfare maximization in combinatorial auctions with submodular valuations. CoRR abs\/1202.2792 (2012). Retrieved from http:\/\/arxiv.org\/abs\/1202.2792."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a011"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_34"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.46"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722208"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.37"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.55"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109624"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0499"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.2307\/1402748"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147956"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133119"},{"key":"e_1_2_1_30_1","volume-title":"Online learning of assignments that maximize submodular functions. arXiv preprint arXiv:0908.0772","author":"Golovin Daniel","year":"2009","unstructured":"Daniel Golovin, Andreas Krause, and Matthew Streeter. 2009. Online learning of assignments that maximize submodular functions. arXiv preprint arXiv:0908.0772 (2009)."},{"key":"e_1_2_1_31_1","volume-title":"Online submodular maximization under a matroid constraint with application to learning assignments. arXiv preprint arXiv:1407.1082","author":"Golovin Daniel","year":"2014","unstructured":"Daniel Golovin, Andreas Krause, and Matthew Streeter. 2014. Online submodular maximization under a matroid constraint with application to learning assignments. arXiv preprint arXiv:1407.1082 (2014)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/562056"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1940179.1940200"},{"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.5555\/646255.758841"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1966.10502008"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.42"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536459"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201913)","volume":"20","author":"Ma Tengyu","year":"2013","unstructured":"Tengyu Ma, Bo Tang, and Yajun Wang. 2013. The simulated greedy algorithm for several submodular matroid secretary problems. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201913) (LIPIcs), Vol. 20. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 478--489."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","unstructured":"G. L. Nemhauser L. A. Wolsey and M. L. Fisher. 1978. An analysis of approximations for maximizing submodular set functions\u2014I. Math. Program. 14 1 (1 Dec. 1978) 265--294. 10.1007\/BF01588971","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/2027127.2027167"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3242770","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3242770","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:22Z","timestamp":1750208242000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3242770"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,17]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,10,31]]}},"alternative-id":["10.1145\/3242770"],"URL":"https:\/\/doi.org\/10.1145\/3242770","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,17]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}