{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T16:39:19Z","timestamp":1779295159270,"version":"3.51.4"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,6,14]],"date-time":"2015-06-14T00:00:00Z","timestamp":1434240000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2016,11]]},"DOI":"10.1007\/s10878-015-9915-5","type":"journal-article","created":{"date-parts":[[2015,6,13]],"date-time":"2015-06-13T04:31:46Z","timestamp":1434169906000},"page":"1197-1216","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Towards the price of leasing online"],"prefix":"10.1007","volume":"32","author":[{"given":"Sebastian","family":"Abshoff","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Kling","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2689-4412","authenticated-orcid":false,"given":"Christine","family":"Markarian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Friedhelm","family":"Meyer\u00a0auf\u00a0der\u00a0Heide","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Pietrzyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,14]]},"reference":[{"key":"9915_CR1","doi-asserted-by":"publisher","unstructured":"Abshoff S, Markarian C, Meyer auf der Heide F (2014) Randomized online algorithms for set cover leasing problems. In: Zhao Z, Lidong W, Wen X, Ding-Zhu D (eds), Combinatorial optimization and applications\u20148th International Conference, COCOA 2014, Wailea, Maui, Dec 19\u201321, 2014, Proceedings, volume 8881 of Lecture Notes in Computer Science, pp 25\u201334. Springer. ISBN 978-3-319-12690-6. doi: 10.1007\/978-3-319-12691-3_3","DOI":"10.1007\/978-3-319-12691-3_3"},{"key":"9915_CR2","doi-asserted-by":"publisher","unstructured":"Alon N, Azar Y, Gutner S (2005) Admission control to minimize rejections and online set cover with repetitions. In: Phillip BG, Paul GS (eds), SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, July 18\u201320, 2005, Las Vegas, Nevada, pp 238\u2013244. ACM. ISBN 1-58113-986-1. doi: 10.1145\/1073970.1074010","DOI":"10.1145\/1073970.1074010"},{"issue":"4","key":"9915_CR3","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1145\/1198513.1198522","volume":"2","author":"N Alon","year":"2006","unstructured":"Alon N, Awerbuch B, Azar Y, Buchbinder N, Naor J (2006a) A general approach to online network optimization problems. ACM Trans. Algoritm. 2(4):640\u2013660. doi: 10.1145\/1198513.1198522","journal-title":"ACM Trans. Algoritm."},{"issue":"2","key":"9915_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/1150334.1150336","volume":"2","author":"N Alon","year":"2006","unstructured":"Alon N, Moshkovitz D, Safra S (2006b) Algorithmic construction of sets for k-restrictions. ACM Trans. Algoritm. 2(2):153\u2013177. doi: 10.1145\/1150334.1150336","journal-title":"ACM Trans. Algoritm."},{"issue":"2","key":"9915_CR5","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, Buchbinder N, Naor J (2009) The online set cover problem. SIAM J. Comput. 39(2):361\u2013370. doi: 10.1137\/060661946","journal-title":"SIAM J. Comput."},{"key":"9915_CR6","doi-asserted-by":"publisher","unstructured":"Anthony BM, Gupta A (2007) Infrastructure leasing problems. In: Matteo F, Williamson DP (eds), Proceedings of the integer programming and combinatorial optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 25\u201327, 2007, volume 4513 of Lecture Notes in Computer Science, pp 424\u2013438. Springer. ISBN 978-3-540-72791-0. doi: 10.1007\/978-3-540-72792-7_32","DOI":"10.1007\/978-3-540-72792-7_32"},{"key":"9915_CR7","unstructured":"Armbrust M, Fox A, Griffith R, Joseph AD, Katz RH, Konwinski A, Lee G, Patterson DA, Rabkin A, Stoica I, Zaharia M (2009) Above the clouds: a Berkeley view of cloud computing. Technical Report UCB\/EECS-2009-28, EECS Department, University of California, Berkeley. URL http:\/\/www.eecs.berkeley.edu\/Pubs\/TechRpts\/2009\/EECS-2009-28.html"},{"issue":"1\u20133","key":"9915_CR8","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.tcs.2007.10.047","volume":"393","author":"P Berman","year":"2008","unstructured":"Berman P, DasGupta B (2008) Approximating the online set multicover problems via randomized winnowing. Theor Comput Sci 393(1\u20133):54\u201371. doi: 10.1016\/j.tcs.2007.10.047","journal-title":"Theor Comput Sci"},{"issue":"6\u20137","key":"9915_CR9","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1016\/j.dam.2004.11.009","volume":"155","author":"P Berman","year":"2007","unstructured":"Berman P, DasGupta B, Sontag ED (2007) Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Discret Appl Math 155(6\u20137):733\u2013749. doi: 10.1016\/j.dam.2004.11.009","journal-title":"Discret Appl Math"},{"key":"9915_CR10","doi-asserted-by":"publisher","unstructured":"Blelloch GE, Tangwongsan K (2010) Parallel approximation algorithms for facility-location problems. In: auf der Heide FM, Phillips CA (eds), SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, Thira, Santorini, Greece, June 13\u201315, 2010, pp 315\u2013324. ACM. ISBN 978-1-4503-0079-7. doi: 10.1145\/1810479.1810535","DOI":"10.1145\/1810479.1810535"},{"issue":"2","key":"9915_CR11","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder N, Naor J (2009) Online primal-dual algorithms for covering and packing. Math Oper Res 34(2):270\u2013286. doi: 10.1287\/moor.1080.0363","journal-title":"Math Oper Res"},{"issue":"3","key":"9915_CR12","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal V (1979) A greedy heuristic for the set-covering problem. Math Oper Res 4(3):233\u2013235","journal-title":"Math Oper Res"},{"key":"9915_CR13","doi-asserted-by":"publisher","unstructured":"de Assun\u00e7\u00e3o MD, di Costanzo A, Buyya R (2009) Evaluating the cost-benefit of using cloud computing to extend the capacity of clusters. In: Kranzlm\u00fcller D, Bode A, Hegering H-G, Casanova H, Gerndt M (eds), Proceedings of the 18th ACM International Symposium on High Performance Distributed Computing, HPDC 2009, Garching, Germany, June 11\u201313, pp 141\u2013150 ACM. ISBN 978-1-60558-587-1. doi: 10.1145\/1551609.1551635","DOI":"10.1145\/1551609.1551635"},{"issue":"4","key":"9915_CR14","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of ln n for approximating set cover. J ACM 45(4):634\u2013652. doi: 10.1145\/285055.285059","journal-title":"J ACM"},{"issue":"1","key":"9915_CR15","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/j.jda.2006.03.001","volume":"5","author":"D Fotakis","year":"2007","unstructured":"Fotakis D (2007) A primal-dual algorithm for online non-uniform facility location. J Discret Algoritm 5(1):141\u2013148. doi: 10.1016\/j.jda.2006.03.001","journal-title":"J Discret Algoritm"},{"issue":"1","key":"9915_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-9049-y","volume":"50","author":"D Fotakis","year":"2008","unstructured":"Fotakis D (2008) On the competitive ratio for online facility location. Algorithmica 50(1):1\u201357. doi: 10.1007\/s00453-007-9049-y","journal-title":"Algorithmica"},{"issue":"2","key":"9915_CR17","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain K, Vazirani VV (2001) Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48(2):274\u2013296. doi: 10.1145\/375827.375845","journal-title":"J. ACM"},{"issue":"3","key":"9915_CR18","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9(3):256\u2013278. doi: 10.1016\/S0022-0000(74)80044-9","journal-title":"J Comput Syst Sci"},{"key":"9915_CR19","doi-asserted-by":"publisher","unstructured":"Kling P, auf der Heide FM, Pietrzyk P (2012) An algorithm for online facility leasing. In: Even G, Halld\u00f3rsson MM (eds), Structural information and communication complexity\u201419th International Colloquium, SIROCCO 2012, Reykjavik, Iceland, June 30-July 2, 2012, Revised Selected Papers, volume 7355 of Lecture Notes in Computer Science, pp 61\u201372. Springer. ISBN 978-3-642-31103-1. doi: 10.1007\/978-3-642-31104-8_6","DOI":"10.1007\/978-3-642-31104-8_6"},{"key":"9915_CR20","unstructured":"Korman S (2004) On the use of randomization in the online set cover problem. Master\u2019s thesis, Weizmann Institute of Science, Rehovot, Israel"},{"issue":"4","key":"9915_CR21","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz L (1975) On the ratio of optimal integral and fractional covers. Discret Math 13(4):383\u2013390","journal-title":"Discret Math"},{"key":"9915_CR22","doi-asserted-by":"publisher","unstructured":"Meyerson A (2001) Online facility location. In: 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14\u201317 Oct 2001, Las Vegas, Nevada, USA, pp 426\u2013431. IEEE Computer Society. ISBN 0-7695-1390-5. doi: 10.1109\/SFCS.2001.959917","DOI":"10.1109\/SFCS.2001.959917"},{"key":"9915_CR23","doi-asserted-by":"publisher","unstructured":"Meyerson A (2005) The parking permit problem. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23\u201325 Oct 2005, Pittsburgh, PA, USA, pp 274\u2013284. IEEE Computer Society. ISBN 0-7695-2468-0. doi: 10.1109\/SFCS.2005.72","DOI":"10.1109\/SFCS.2005.72"},{"issue":"4","key":"9915_CR24","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/j.disopt.2013.10.001","volume":"10","author":"C Nagarajan","year":"2013","unstructured":"Nagarajan C, Williamson DP (2013) Offline and online facility leasing. Discret Optim 10(4):361\u2013370. doi: 10.1016\/j.disopt.2013.10.001","journal-title":"Discret Optim"},{"key":"9915_CR25","doi-asserted-by":"publisher","unstructured":"Pandit S, Pemmaraju SV (2010) Rapid randomized pruning for fast greedy distributed algorithms. In: Richa AW, Guerraoui R (eds), Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, PODC 2010, Zurich, Switzerland, July 25\u201328, 2010, pp 325\u2013334. ACM. ISBN 978-1-60558-888-9. doi: 10.1145\/1835698.1835777","DOI":"10.1145\/1835698.1835777"},{"key":"9915_CR26","unstructured":"Vazirani VV (2001) Approximation algorithms. Springer, Berlin. ISBN 978-3-540-65367-7. URL http:\/\/www.springer.com\/computer\/theoretical+computer+science\/book\/978-3-540-65367-7"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9915-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-015-9915-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9915-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-015-9915-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:23:27Z","timestamp":1559262207000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-015-9915-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,14]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["9915"],"URL":"https:\/\/doi.org\/10.1007\/s10878-015-9915-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,14]]}}}