{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T10:00:41Z","timestamp":1743156041023,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030046507"},{"type":"electronic","value":"9783030046514"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-030-04651-4_41","type":"book-chapter","created":{"date-parts":[[2018,11,15]],"date-time":"2018-11-15T19:56:50Z","timestamp":1542311810000},"page":"609-623","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Online Unit Covering in Euclidean Space"],"prefix":"10.1007","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[]},{"given":"Anirban","family":"Ghosh","sequence":"additional","affiliation":[]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"issue":"2","key":"41_CR1","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."},{"key":"41_CR2","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1016\/j.comgeo.2016.04.002","volume":"60","author":"A Biniaz","year":"2017","unstructured":"Biniaz, A., Liu, P., Maheshwari, A., Smid, M.H.M.: Approximation algorithms for the unit disk cover problem in 2D and 3D. Comput. Geom. 60, 8\u201318 (2017)","journal-title":"Comput. Geom."},{"key":"41_CR3","volume-title":"Online Computation and Competitive Analysis","author":"A Borodin","year":"1998","unstructured":"Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)"},{"key":"41_CR4","first-page":"507","volume":"38","author":"P Boyvalenkov","year":"2012","unstructured":"Boyvalenkov, P., Dodunekov, S., Musin, O.R.: A survey on the kissing numbers. Serdica Math. J. 38, 507\u2013522 (2012)","journal-title":"Serdica Math. J."},{"key":"41_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-29929-7","volume-title":"Research Problems in Discrete Geometry","author":"P Brass","year":"2005","unstructured":"Brass, P., Moser, W.O.J., Pach, J.: Research Problems in Discrete Geometry. Springer, New York (2005). https:\/\/doi.org\/10.1007\/0-387-29929-7"},{"issue":"2","key":"41_CR6","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-dual algorithms for covering and packing. Math. Oper. Res. 34(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"41_CR7","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1007\/s00224-007-9085-7","volume":"45","author":"TM Chan","year":"2009","unstructured":"Chan, T.M., Zarrabi-Zadeh, H.: A randomized algorithm for online unit clustering. Theory Comput. Syst. 45(3), 486\u2013496 (2009)","journal-title":"Theory Comput. Syst."},{"issue":"6","key":"41_CR8","doi-asserted-by":"publisher","first-page":"1417","DOI":"10.1137\/S0097539702418498","volume":"33","author":"M Charikar","year":"2004","unstructured":"Charikar, M., Chekuri, C., Feder, T., Motwani, R.: Incremental clustering and dynamic information retrieval. SIAM J. Comput. 33(6), 1417\u20131440 (2004)","journal-title":"SIAM J. Comput."},{"key":"41_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-319-89441-6_18","volume-title":"Approximation and Online Algorithms","author":"A Dumitrescu","year":"2018","unstructured":"Dumitrescu, A., T\u00f3th, C.D.: Online unit clustering in higher dimensions. In: Solis-Oba, R., Fleischer, R. (eds.) WAOA 2017. LNCS, vol. 10787, pp. 238\u2013252. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-89441-6_18"},{"key":"41_CR10","doi-asserted-by":"crossref","first-page":"R22","DOI":"10.37236\/1360","volume":"5","author":"Y Edel","year":"1998","unstructured":"Edel, Y., Rains, E.M., Sloane, N.J.A.: On kissing numbers in dimensions 32 to 128. Electr. J. Comb. 5, R22 (1998)","journal-title":"Electr. J. Comb."},{"key":"41_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2013.07.008","volume":"500","author":"MR Ehmsen","year":"2013","unstructured":"Ehmsen, M.R., Larsen, K.S.: Better bounds on online unit clustering. Theor. Comput. Sci. 500, 1\u201324 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"41_CR12","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/1868237.1868245","volume":"7","author":"L Epstein","year":"2010","unstructured":"Epstein, L., van Stee, R.: On the online unit clustering problem. ACM Trans. Algorithms 7(1), 7:1\u20137:18 (2010)","journal-title":"ACM Trans. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.H.: Optimal algorithms for approximate clustering. In: Proceedings of 20th ACM Symposium on Theory of Computing (STOC), pp. 434\u2013444 (1988)","key":"41_CR13","DOI":"10.1145\/62212.62255"},{"issue":"3","key":"41_CR14","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"RJ Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M., Tanimoto, S.L.: Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett. 12(3), 133\u2013137 (1981)","journal-title":"Inf. Process. Lett."},{"key":"41_CR15","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"41_CR16","volume-title":"Combinatorial Geometry in the Plane","author":"H Hadwiger","year":"1964","unstructured":"Hadwiger, H., Debrunner, H.: Combinatorial Geometry in the Plane. Holt, Rinehart and Winston, New York (1964). (English translation by Victor Klee)"},{"issue":"1","key":"41_CR17","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"DS Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130\u2013136 (1985)","journal-title":"J. ACM"},{"key":"41_CR18","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/j.aim.2018.07.001","volume":"335","author":"M Jenssen","year":"2018","unstructured":"Jenssen, M., Joos, F., Perkins, W.: On kissing numbers and spherical codes in high dimensions. Adv. Math. 335, 307\u2013321 (2018)","journal-title":"Adv. Math."},{"issue":"1","key":"41_CR19","first-page":"1","volume":"14","author":"GA Kabatiansky","year":"1978","unstructured":"Kabatiansky, G.A., Levenshtein, V.I.: On bounds for packings on the sphere and in space. Probl. Inform. Transm. 14(1), 1\u201317 (1978)","journal-title":"Probl. Inform. Transm."},{"key":"41_CR20","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/j.tcs.2015.06.055","volume":"600","author":"J Kawahara","year":"2015","unstructured":"Kawahara, J., Kobayashi, K.M.: An improved lower bound for one-dimensional online unit clustering. Theor. Comput. Sci. 600, 171\u2013173 (2015)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"41_CR21","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s10878-009-9216-y","volume":"20","author":"C Liao","year":"2010","unstructured":"Liao, C., Hu, S.: Polynomial time approximation schemes for minimum disk cover problems. J. Comb. Optim. 20(4), 399\u2013412 (2010)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"41_CR22","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N Megiddo","year":"1984","unstructured":"Megiddo, N., Supowit, K.J.: On the complexity of some common geometric location problems. SIAM J. Comput. 13(1), 182\u2013196 (1984)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"41_CR23","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s00454-010-9285-9","volume":"44","author":"NH Mustafa","year":"2010","unstructured":"Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete Comput. Geom. 44(4), 883\u2013895 (2010)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"41_CR24","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1017\/S2040618500033219","volume":"2","author":"RA Rankin","year":"1955","unstructured":"Rankin, R.A.: The closest packing of spherical caps in $$n$$ dimensions. Proc. Glasgow Math. Assoc. 2(3), 139\u2013144 (1955)","journal-title":"Proc. Glasgow Math. Assoc."},{"key":"41_CR25","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)"},{"issue":"6","key":"41_CR26","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1002\/j.1538-7305.1965.tb04170.x","volume":"44","author":"AD Wyner","year":"1965","unstructured":"Wyner, A.D.: Capabilities of bounded discrepancy decoding. Bell Syst. Tech. J. 44(6), 1061\u20131122 (1965)","journal-title":"Bell Syst. Tech. J."},{"unstructured":"Wynn, E.: Covering a unit ball with balls half the radius (2012). https:\/\/mathoverflow.net\/questions\/98007\/covering-a-unit-ball-with-balls-half-the-radius","key":"41_CR27"},{"issue":"4","key":"41_CR28","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/s00453-008-9208-9","volume":"54","author":"H Zarrabi-Zadeh","year":"2009","unstructured":"Zarrabi-Zadeh, H., Chan, T.M.: An improved algorithm for online unit clustering. Algorithmica 54(4), 490\u2013500 (2009)","journal-title":"Algorithmica"}],"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-030-04651-4_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T15:51:23Z","timestamp":1710345083000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-04651-4_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783030046507","9783030046514"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-04651-4_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"16 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Atlanta, GA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spacl.kennesaw.edu\/cocoa2018\/cfp.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}