{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:27Z","timestamp":1740122427777,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T00:00:00Z","timestamp":1662163200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T00:00:00Z","timestamp":1662163200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s10878-022-00898-3","type":"journal-article","created":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T20:21:42Z","timestamp":1662236502000},"page":"3364-3404","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Online algorithms for the maximum k-interval coverage problem"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3941-8490","authenticated-orcid":false,"given":"Songhua","family":"Li","sequence":"first","affiliation":[]},{"given":"Minming","family":"Li","sequence":"additional","affiliation":[]},{"given":"Lingjie","family":"Duan","sequence":"additional","affiliation":[]},{"given":"Victor C. S.","family":"Lee","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,3]]},"reference":[{"key":"898_CR1","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.tcs.2021.02.022","volume":"863","author":"S Albers","year":"2021","unstructured":"Albers S, Ladewig L (2021) New results for the $$k$$-secretary problem. Theoret Comput Sci 863:102\u2013119. https:\/\/doi.org\/10.1016\/j.tcs.2021.02.022","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"898_CR2","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1137\/060661946","volume":"39","author":"N Alon","year":"2009","unstructured":"Alon N, Awerbuch B, Azar Y et al (2009) The online set cover problem. SIAM J Comput 39(2):361\u2013370. https:\/\/doi.org\/10.1137\/060661946","journal-title":"SIAM J Comput"},{"issue":"3","key":"898_CR3","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1137\/16M1095482","volume":"50","author":"S Assadi","year":"2019","unstructured":"Assadi S, Khanna S, Li Y (2019) Tight bounds for single-pass streaming complexity of the set cover problem. SIAM J Comput 50(3):16\u2013341. https:\/\/doi.org\/10.1137\/16M1095482","journal-title":"SIAM J Comput"},{"issue":"13\u201314","key":"898_CR4","doi-asserted-by":"publisher","first-page":"1901","DOI":"10.1016\/j.dam.2012.04.005","volume":"160","author":"G Ausiello","year":"2012","unstructured":"Ausiello G, Boria N, Giannakos A et al (2012) Online maximum $$k$$-coverage. Discret Appl Math 160(13\u201314):1901\u20131913. https:\/\/doi.org\/10.1016\/j.dam.2012.04.005","journal-title":"Discret Appl Math"},{"key":"898_CR5","doi-asserted-by":"publisher","unstructured":"Babaioff M, Immorlica N, Kempe D, et\u00a0al (2007) A knapsack secretary problem with applications. In: Proceedings of approximation, randomization, and combinatorial optimization. Algorithms and techniques. Springer, pp 16\u201328. https:\/\/doi.org\/10.1007\/978-3-540-74208-1_2","DOI":"10.1007\/978-3-540-74208-1_2"},{"issue":"4","key":"898_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2500121","volume":"9","author":"M Bateni","year":"2013","unstructured":"Bateni M, Hajiaghayi M, Zadimoghaddam M (2013) Submodular secretary problem and extensions. ACM Trans Algorithms 9(4):1\u201323. https:\/\/doi.org\/10.1145\/2500121","journal-title":"ACM Trans Algorithms"},{"key":"898_CR7","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1016\/j.chb.2015.08.031","volume":"54","author":"AM Brawley","year":"2016","unstructured":"Brawley AM, Pury CL (2016) Work experiences on mturk: job satisfaction, turnover, and information sharing. Comput Hum Behav 54:531\u2013546. https:\/\/doi.org\/10.1016\/j.chb.2015.08.031","journal-title":"Comput Hum Behav"},{"issue":"3","key":"898_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3309764","volume":"15","author":"N Buchbinder","year":"2019","unstructured":"Buchbinder N, Feldman S, Schwartz R (2019) Online submodular maximization with preemption. ACM Trans Algorithms 15(3):1\u201331. https:\/\/doi.org\/10.1145\/3309764","journal-title":"ACM Trans Algorithms"},{"issue":"2","key":"898_CR9","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/j.jda.2005.03.005","volume":"4","author":"FY Chin","year":"2006","unstructured":"Chin FY, Chrobak M, Fung SP et al (2006) Online competitive algorithms for maximizing weighted throughput of unit jobs. J Discrete Algorithms 4(2):255\u2013276. https:\/\/doi.org\/10.1016\/j.jda.2005.03.005","journal-title":"J Discrete Algorithms"},{"issue":"6","key":"898_CR10","doi-asserted-by":"publisher","first-page":"1709","DOI":"10.1137\/S0097539704446608","volume":"36","author":"M Chrobak","year":"2007","unstructured":"Chrobak M, Jawor W, Sgall J et al (2007) Online scheduling of equal-length jobs: Randomization and restarts help. SIAM J Comput 36(6):1709\u20131728. https:\/\/doi.org\/10.1137\/S0097539704446608","journal-title":"SIAM J Comput"},{"issue":"2","key":"898_CR11","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s10479-018-3025-6","volume":"275","author":"R Cohen","year":"2019","unstructured":"Cohen R, Gonen M (2019) On interval and circular-arc covering problems. Ann Oper Res 275(2):281\u2013295. https:\/\/doi.org\/10.1007\/s10479-018-3025-6","journal-title":"Ann Oper Res"},{"issue":"2","key":"898_CR12","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1137\/16M1105220","volume":"47","author":"M Feldman","year":"2018","unstructured":"Feldman M, Zenklusen R (2018) The submodular secretary problem goes linear. SIAM J Comput 47(2):330\u2013366. https:\/\/doi.org\/10.1137\/16M1105220","journal-title":"SIAM J Comput"},{"key":"898_CR13","doi-asserted-by":"publisher","unstructured":"Feldman M, Svensson O, Zenklusen R (2018) A framework for the secretary problem on the intersection of matroids. In: Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms. SIAM, pp 735\u2013752. https:\/\/doi.org\/10.1137\/1.9781611975031.48","DOI":"10.1137\/1.9781611975031.48"},{"issue":"6","key":"898_CR14","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1002\/(SICI)1520-6750(199809)45:6<615::AID-NAV5>3.0.CO;2-5","volume":"45","author":"DS Hochbaum","year":"1998","unstructured":"Hochbaum DS, Pathria A (1998) Analysis of the greedy approach in problems of maximum $$k$$-coverage. Naval Res Logist 45(6):615\u2013627","journal-title":"Naval Res Logist"},{"key":"898_CR15","doi-asserted-by":"publisher","unstructured":"Iwama K, Taketomi S (2002) Removable online knapsack problems. In: International colloquium on automata, languages, and programming. Springer, pp 293\u2013305. https:\/\/doi.org\/10.1007\/3-540-45465-9_26","DOI":"10.1007\/3-540-45465-9_26"},{"issue":"1","key":"898_CR16","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S Khuller","year":"1999","unstructured":"Khuller S, Moss A, Naor JS (1999) The budgeted maximum coverage problem. Inf Process Lett 70(1):39\u201345. https:\/\/doi.org\/10.1016\/S0020-0190(99)00031-9","journal-title":"Inf Process Lett"},{"issue":"4","key":"898_CR17","first-page":"284","volume":"84","author":"V Klee","year":"1977","unstructured":"Klee V (1977) Can the measure of be computed in less than $$o (n \\log n)$$ steps? Am Math Mon 84(4):284\u2013285","journal-title":"Am Math Mon"},{"key":"898_CR18","unstructured":"Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. In: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, pp 630\u2013631"},{"issue":"115310","key":"898_CR19","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.eswa.2021.115310","volume":"183","author":"L Li","year":"2021","unstructured":"Li L, Wei Z, Hao J et al (2021) Probability learning based tabu search for the budgeted maximum coverage problem. Expert Syst Appl 183(115310):16\u2013341. https:\/\/doi.org\/10.1016\/j.eswa.2021.115310","journal-title":"Expert Syst Appl"},{"key":"898_CR20","doi-asserted-by":"publisher","unstructured":"Li S, Li M, Duan L, et\u00a0al (2020) Online maximum $$k$$-interval coverage problem. In: Proceedings of international conference on combinatorial optimization and applications. Springer, pp 455\u2013470. https:\/\/doi.org\/10.1007\/978-3-540-74208-1_2","DOI":"10.1007\/978-3-540-74208-1_2"},{"issue":"9","key":"898_CR21","doi-asserted-by":"publisher","first-page":"2989","DOI":"10.1007\/s00453-021-00850-7","volume":"83","author":"D Rawitz","year":"2021","unstructured":"Rawitz D, Ros\u00e9n A (2021) Online budgeted maximum coverage. Algorithmica 83(9):2989\u20133014. https:\/\/doi.org\/10.1007\/s00453-021-00850-7","journal-title":"Algorithmica"},{"key":"898_CR22","doi-asserted-by":"publisher","unstructured":"Saha B, Getoor L (2009) On maximum coverage in the streaming model and application to multi-topic blog-watch. In: Proceedings of the 2009 siam international conference on data mining. SIAM, pp 697\u2013708. https:\/\/doi.org\/10.1137\/1.9781611972795.60","DOI":"10.1137\/1.9781611972795.60"},{"key":"898_CR23","doi-asserted-by":"publisher","unstructured":"Vaze R (2018) Online knapsack problem under expected capacity constraint. In: Proceedings of IEEE INFOCOM 2018\u2014IEEE conference on computer communications, pp 2159\u20132167. https:\/\/doi.org\/10.1109\/INFOCOM.2018.8485980","DOI":"10.1109\/INFOCOM.2018.8485980"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00898-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00898-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00898-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T09:40:02Z","timestamp":1667036402000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00898-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,3]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["898"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00898-3","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,9,3]]},"assertion":[{"value":"16 August 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 September 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interests"}}]}}