{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T04:21:51Z","timestamp":1747196511791,"version":"3.40.5"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319126906"},{"type":"electronic","value":"9783319126913"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12691-3_3","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T21:11:32Z","timestamp":1415999492000},"page":"25-34","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Randomized Online Algorithms for Set Cover Leasing Problems"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"Abshoff","sequence":"first","affiliation":[]},{"given":"Christine","family":"Markarian","sequence":"additional","affiliation":[]},{"given":"Friedhelm","family":"Meyer auf der Heide","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,13]]},"reference":[{"key":"3_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/978-3-540-72792-7_32","volume-title":"Integer Programming and Combinatorial Optimization","author":"BM Anthony","year":"2007","unstructured":"Anthony, B.M., Gupta, A.: Infrastructure leasing problems. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol. 4513, pp. 424\u2013438. Springer, Heidelberg (2007)"},{"doi-asserted-by":"crossref","unstructured":"Alon, N., Azar, Y., Gutner, S.: Admission control to minimize rejections and online set cover with repetitions. In: 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Prague, pp. 238\u2013244 (2005)","key":"3_CR2","DOI":"10.1145\/1073970.1074010"},{"issue":"13","key":"3_CR3","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., DasGubta, B.: Approximating the online set multicover problems via randomized winnowing. Theor. Comput. Sci. 393(13), 54\u201371 (2008)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N.: A general approach to online network optimization problems. In: 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, LA, pp. 577\u2013586 (2004)","key":"3_CR4"},{"key":"3_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-642-31104-8_6","volume-title":"Structural Information and Communication Complexity","author":"P Kling","year":"2012","unstructured":"Kling, P., Meyer auf der Heide, F., Pietrzyk, P.: An algorithm for online facility leasing. In: Even, G., Halld\u00f3rsson, M.M. (eds.) SIROCCO 2012. LNCS, vol. 7355, pp. 61\u201372. Springer, Heidelberg (2012)"},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-540-68891-4_21","volume-title":"Integer Programming and Combinatorial Optimization","author":"C Nagarajan","year":"2008","unstructured":"Nagarajan, C., Williamson, D.P.: Offline and online facility leasing. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol. 5035, pp. 303\u2013315. Springer, Heidelberg (2008)"},{"issue":"3","key":"3_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chavatal","year":"1979","unstructured":"Chavatal, 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":"3_CR8","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"},{"unstructured":"Feige, U., Korman, S.: Personal communication","key":"3_CR9"},{"key":"3_CR10","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, 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lovasz","year":"1975","unstructured":"Lovasz, L.: On the ratio of optimal and fractional covers. Discrete Math. 13, 383\u2013390 (1975)","journal-title":"Discrete Math."},{"issue":"67","key":"3_CR12","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.: Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks. Discrete Appl. Math. 155(67), 733\u2013749 (2007)","journal-title":"Discrete Appl. Math."},{"unstructured":"Vazirani, V.: Approximation Algorithms (2001)","key":"3_CR13"},{"key":"3_CR14","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-dual algorithm for online non-uniform facility location. J. Discrete Algorithms 5, 141\u2013148 (2007)","journal-title":"J. Discrete Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. In: 35th Annual ACM Symposium on the Theory of Computation (STOC), San Diego, CA, USA, pp. 100\u2013105 (2003)","key":"3_CR15","DOI":"10.1145\/780542.780558"},{"doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Fiat, A., Leighton, T.: Making commitments in the face of uncertainty: how to pick a winner almost every time. In: 28th Annual ACM Symposium on Theory of Computing (STOC), Pennsylvania, USA, pp. 519\u2013530 (1996)","key":"3_CR16","DOI":"10.1145\/237814.238000"},{"doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), Las Vegas, Nevada, USA, pp. 426\u2013431 (2001)","key":"3_CR17","DOI":"10.1109\/SFCS.2001.959917"},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1007\/3-540-45061-0_51","volume-title":"Automata, Languages and Programming","author":"D Fotakis","year":"2003","unstructured":"Fotakis, D.: On the competitive ratio for online facility location. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 637\u2013652. Springer, Heidelberg (2003)"},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1007\/11561071_61","volume-title":"Algorithms \u2013 ESA 2005","author":"N Buchbinder","year":"2005","unstructured":"Buchbinder, N., Naor, J.S.: Online primal-dual algorithms for covering and packing problems. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 689\u2013701. Springer, Heidelberg (2005)"},{"doi-asserted-by":"crossref","unstructured":"Meyerson, A.: The parking permit problem. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Pittsburgh, PA, USA, pp. 274\u2013284 (2005)","key":"3_CR20","DOI":"10.1109\/SFCS.2005.72"},{"unstructured":"Malik, S., Huet, F.: Virtual cloud: rent out the rented resources. In: 6th IEEE International Conference for Internet Technology and Secured Transactions (ICITST), Abu Dhabi, UAE, pp. 536\u2013541 (2011)","key":"3_CR21"},{"key":"3_CR22","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, 153\u2013177 (2006)","journal-title":"ACM Trans. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12691-3_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:25:57Z","timestamp":1747160757000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-12691-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319126906","9783319126913"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12691-3_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"13 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}