{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T16:18:33Z","timestamp":1770135513592,"version":"3.49.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2018,2,20]],"date-time":"2018-02-20T00:00:00Z","timestamp":1519084800000},"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":["Algorithmica"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s00453-018-0420-y","type":"journal-article","created":{"date-parts":[[2018,2,20]],"date-time":"2018-02-20T14:46:39Z","timestamp":1519137999000},"page":"1556-1574","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Towards Flexible Demands in Online Leasing Problems"],"prefix":"10.1007","volume":"80","author":[{"given":"Shouwei","family":"Li","sequence":"first","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 auf der Heide","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,2,20]]},"reference":[{"issue":"4","key":"420_CR1","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1007\/s10878-015-9915-5","volume":"32","author":"S Abshoff","year":"2016","unstructured":"Abshoff, S., Kling, P., Markarian, C., Meyer auf der Heide, F., Pietrzyk, P.: Towards the price of leasing online. J. Comb. Optim. 32(4), 1197\u20131216 (2016)","journal-title":"J. Comb. Optim."},{"key":"420_CR2","doi-asserted-by":"crossref","unstructured":"Abshoff, S., Markarian, C., Meyer auf der Heide, F.: Randomized online algorithms for set cover leasing problems. In: Combinatorial Optimization and Applications\u20148th International Conference, COCOA 2014, Wailea, Maui, HI, USA, 19\u201321 December 2014, Proceedings, pp. 25\u201334 (2014)","DOI":"10.1007\/978-3-319-12691-3_3"},{"issue":"2","key":"420_CR3","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.: The online set cover problem. SIAM J. Comput. 39(2), 361\u2013370 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"420_CR4","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.S.: A general approach to online network optimization problems. ACM Trans. Algorithms 2(4), 640\u2013660 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"420_CR5","doi-asserted-by":"crossref","unstructured":"Alon, N., Azar, Y., Gutner, S.: Admission control to minimize rejections and online set cover with repetitions. In: Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA \u201905, pp. 238\u2013244. ACM, New York (2005)","DOI":"10.1145\/1073970.1074010"},{"issue":"2","key":"420_CR6","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.: Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms 2(2), 153\u2013177 (2006)","journal-title":"ACM Trans. Algorithms"},{"key":"420_CR7","doi-asserted-by":"crossref","unstructured":"Anthony, B.M., Gupta, A.: Infrastructure leasing problems. In: IPCO, pp. 424\u2013438 (2007)","DOI":"10.1007\/978-3-540-72792-7_32"},{"key":"420_CR8","unstructured":"Ausiello, G., Giannakos, A., Paschos, V.T.: Greedy algorithms for online set covering and related problems. In: Proceedings of the Twelfth Computing: The Australasian Theory Symposium\u2014vol. 51, CATS \u201906, pp. 145\u2013151. Australian Computer Society, Inc., Darlinghurst (2006)"},{"key":"420_CR9","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y.: Buy-at-bulk network design. In: 38th Annual Symposium on Foundations of Computer Science, FOCS \u201997, Miami Beach, Florida, USA, 19\u201322 October 1997, pp. 542\u2013547 (1997)","DOI":"10.1109\/SFCS.1997.646143"},{"issue":"1\u20133","key":"420_CR10","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.: Approximating the online set multicover problems via randomized winnowing. Theor. Comput. Sci. 393(1\u20133), 54\u201371 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"6\u20137","key":"420_CR11","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, E.D.: Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Discrete Appl. Math. 155(6\u20137), 733\u2013749 (2007)","journal-title":"Discrete Appl. Math."},{"key":"420_CR12","unstructured":"Bhawalkar, K., Gollapudi, S., Panigrahi, D.: Online set cover with set requests. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2014, 4\u20136 September 2014, Barcelona, Spain, pp. 64\u201379 (2014)"},{"issue":"2","key":"420_CR13","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.: Online primal\u2013dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"420_CR14","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10107-004-0524-9","volume":"102","author":"FA Chudak","year":"2005","unstructured":"Chudak, F.A., Williamson, D.P.: Improved approximation algorithms for capacitated facility location problems. Math. Program. 102(2), 207\u2013222 (2005)","journal-title":"Math. Program."},{"issue":"3","key":"420_CR15","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"420_CR16","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"420_CR17","doi-asserted-by":"crossref","unstructured":"Fotakis, D.: On the competitive ratio for online facility location. In: Proceedings of the 30th International Conference on Automata, Languages and Programming, ICALP\u201903, pp. 637\u2013652. Springer, Berlin (2003)","DOI":"10.1007\/3-540-45061-0_51"},{"issue":"1","key":"420_CR18","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.: A primal\u2013dual algorithm for online non-uniform facility location. J. Discrete Algorithms 5(1), 141\u2013148 (2007)","journal-title":"J. Discrete Algorithms"},{"key":"420_CR19","doi-asserted-by":"crossref","unstructured":"Freund, A., Rawitz, D.: Combinatorial interpretations of dual fitting and primal fitting. In: Approximation and Online Algorithms, First International Workshop, WAOA 2003, Budapest, Hungary, 16\u201318 September 2003, Revised Papers, pp. 137\u2013150 (2003)","DOI":"10.1007\/978-3-540-24592-6_11"},{"key":"420_CR20","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: Improved facility location algorithms. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201998, pp. 649\u2013657. Society for Industrial and Applied Mathematics, Philadelphia (1998)"},{"issue":"3","key":"420_CR21","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1236457.1236458","volume":"54","author":"A Gupta","year":"2007","unstructured":"Gupta, A., Kumar, A., P\u00e1l, M., Roughgarden, T.: Approximation via cost sharing: simpler and better approximation algorithms for network design. J. ACM 54(3), 11 (2007)","journal-title":"J. ACM"},{"issue":"6","key":"420_CR22","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J. ACM 50(6), 795\u2013824 (2003)","journal-title":"J. ACM"},{"issue":"2","key":"420_CR23","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal\u2013dual schema and Lagrangian relaxation. J. ACM 48(2), 274\u2013296 (2001)","journal-title":"J. ACM"},{"issue":"3","key":"420_CR24","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9(3), 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"420_CR25","doi-asserted-by":"crossref","unstructured":"Kling, P., Meyer auf der Heide, F., Pietrzyk, P.: An algorithm for online facility leasing. In: Structural Information and Communication Complexity\u201419th International Colloquium, SIROCCO 2012, Reykjavik, Iceland, June 30\u2013July 2, 2012, Revised Selected Papers, pp. 61\u201372 (2012)","DOI":"10.1007\/978-3-642-31104-8_6"},{"key":"420_CR26","unstructured":"Korman, S.: On the use of randomization in the online set cover problem. Master\u2019s thesis, Weizmann Institute of Science, Rehovot (2004)"},{"key":"420_CR27","doi-asserted-by":"crossref","unstructured":"Li, S.: A 1.488 approximation algorithm for the uncapacitated facility location problem. In: Proceedings of the 38th International Conference on Automata, Languages and Programming\u2014Volume Part II, ICALP\u201911, pp. 77\u201388. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-22012-8_5"},{"key":"420_CR28","doi-asserted-by":"crossref","unstructured":"Li, S., M\u00e4cker, A., Markarian, C., Meyer auf der Heide, F., Riechers, S.: Towards flexible demands in online leasing problems. In: Computing and Combinatorics\u201421st International Conference, COCOON 2015, Beijing, China, 4\u20136 August 2015, Proceedings, pp. 277\u2013288 (2015)","DOI":"10.1007\/978-3-319-21398-9_22"},{"issue":"4","key":"420_CR29","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13(4), 383\u2013390 (1975)","journal-title":"Discrete Math."},{"key":"420_CR30","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 229\u2013242 (2002)","DOI":"10.1007\/3-540-45753-4_20"},{"issue":"3","key":"420_CR31","doi-asserted-by":"publisher","first-page":"816","DOI":"10.1137\/S0097539701383443","volume":"32","author":"RR Mettu","year":"2003","unstructured":"Mettu, R.R., Plaxton, C.G.: The online median problem. SIAM J. Comput. 32(3), 816\u2013832 (2003)","journal-title":"SIAM J. Comput."},{"key":"420_CR32","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, FOCS \u201901, pp. 426\u2013431. IEEE Computer Society, Washington (2001)","DOI":"10.1109\/SFCS.2001.959917"},{"key":"420_CR33","doi-asserted-by":"crossref","unstructured":"Meyerson, A.M.: The parking permit problem. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201905, pp. 274\u2013284. IEEE Computer Society, Washington (2005)","DOI":"10.1109\/SFCS.2005.72"},{"issue":"4","key":"420_CR34","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, D.P.: Offline and online facility leasing. Discrete Optim. 10(4), 361\u2013370 (2013)","journal-title":"Discrete Optim."},{"key":"420_CR35","unstructured":"Salman, F.S., Cheriyan, J., Ravi, R., Subramanian, S.: Buy-at-bulk network design: approximating the single-sink edge installation problem. In: Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201997, pp. 619\u2013628. Society for Industrial and Applied Mathematics, Philadelphia (1997)"},{"key":"420_CR36","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, E., Aardal, K.: Approximation algorithms for facility location problems (extended abstract). In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC \u201997, pp. 265\u2013274. ACM, New York (1997)","DOI":"10.1145\/258533.258600"},{"key":"420_CR37","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, New York (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0420-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0420-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0420-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T02:42:23Z","timestamp":1570761743000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0420-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,20]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["420"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0420-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,20]]},"assertion":[{"value":"25 October 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}