{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T16:59:04Z","timestamp":1774803544183,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T00:00:00Z","timestamp":1641427200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T00:00:00Z","timestamp":1641427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1422311 and CCF-1423615"],"award-info":[{"award-number":["CCF-1422311 and CCF-1423615"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,5]]},"DOI":"10.1007\/s00453-021-00916-6","type":"journal-article","created":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T14:02:48Z","timestamp":1641477768000},"page":"1213-1231","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Online Unit Clustering and Unit Covering in Higher Dimensions"],"prefix":"10.1007","volume":"84","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8769-3190","authenticated-orcid":false,"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,1,6]]},"reference":[{"issue":"2","key":"916_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":"916_CR2","doi-asserted-by":"crossref","unstructured":"Azar, Y., Niv Buchbinder, T.-H., Chan, H., Chen, S., Cohen, I.R., Gupta, A., Huang, Z., Kang, N., Nagarajan, V., Naor, J., Debmalya, P.: Online algorithms for covering and packing problems with convex objectives. In: Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS), pp.\u00a0148\u2013157. IEEE (2016)","DOI":"10.1109\/FOCS.2016.24"},{"key":"916_CR3","doi-asserted-by":"crossref","unstructured":"Azar, Y., Bhaskar, U., Fleischer, L., Panigrahi, D.: Online mixed packing and covering. In: Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a085\u2013100. SIAM (2013)","DOI":"10.1137\/1.9781611973105.6"},{"key":"916_CR4","doi-asserted-by":"crossref","unstructured":"Azar, Y., Cohen, I.R., Roytman, A.: Online lower bounds via duality. In: Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a01038\u20131050. SIAM (2017)","DOI":"10.1137\/1.9781611974782.66"},{"issue":"1","key":"916_CR5","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/BF01294260","volume":"11","author":"S Ben-David","year":"1994","unstructured":"Ben-David, S., Borodin, A., Karp, R.M., Tardos, G., Wigderson, A.: On the power of randomization in on-line algorithms. Algorithmica 11(1), 2\u201314 (1994)","journal-title":"Algorithmica"},{"key":"916_CR6","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.: Approximation algorithms for the unit disk cover problem in 2D and 3D. Comput. Geom. 60, 8\u201318 (2017)","journal-title":"Comput. Geom."},{"key":"916_CR7","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":"916_CR8","volume-title":"Research Problems in Discrete Geometry","author":"P Brass","year":"2005","unstructured":"Brass, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer, New York (2005)"},{"issue":"2","key":"916_CR9","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":"916_CR10","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. Theor. Comput. Syst. 45(3), 486\u2013496 (2009)","journal-title":"Theor. Comput. Syst."},{"issue":"6","key":"916_CR11","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."},{"issue":"3","key":"916_CR12","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/1412700.1412719","volume":"39","author":"M Chrobak","year":"2008","unstructured":"Chrobak, M.: SIGACT news online algorithms column 13. SIGACT News Bull. 39(3), 96\u2013121 (2008)","journal-title":"SIGACT News Bull."},{"issue":"2","key":"916_CR13","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/s00453-011-9586-2","volume":"65","author":"J Csirik","year":"2013","unstructured":"Csirik, J., Epstein, L., Imreh, C., Levin, A.: Online clustering with variable sized clusters. Algorithmica 65(2), 251\u2013274 (2013)","journal-title":"Algorithmica"},{"issue":"4","key":"916_CR14","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/s11081-013-9231-9","volume":"14","author":"G Div\u00e9ki","year":"2013","unstructured":"Div\u00e9ki, G., Imreh, C.: An online 2-dimensional clustering problem with variable sized clusters. Optimization and Engineering 14(4), 575\u2013593 (2013)","journal-title":"Optimization and Engineering"},{"key":"916_CR15","doi-asserted-by":"crossref","unstructured":"Div\u00e9ki, G., Imreh, C.: Grid based online algorithms for clustering problems. In: Proceedings of the 15th IEEE International Symposium on Computational Intelligence and Informatics (CINTI), pp.\u00a0159. IEEE (2014)","DOI":"10.1109\/CINTI.2014.7028668"},{"issue":"4","key":"916_CR16","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/3300150.3300161","volume":"49","author":"A Dumitrescu","year":"2018","unstructured":"Dumitrescu, A.: Computational geometry column 68. SIGACT News 49(4), 46\u201354 (2018)","journal-title":"SIGACT News"},{"key":"916_CR17","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.tcs.2019.12.010","volume":"809","author":"A Dumitrescu","year":"2020","unstructured":"Dumitrescu, A., Ghosh, A., T\u00f3th, C.D.: Online unit covering in Euclidean space. Theor. Comput. Sci. 809, 218\u2013230 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"916_CR18","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\u20133","key":"916_CR19","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.tcs.2008.04.046","volume":"407","author":"L Epstein","year":"2008","unstructured":"Epstein, L., Levin, A., van Stee, R.: Online unit clustering: variations on a theme. Theor. Comput. Sci. 407(1\u20133), 85\u201396 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"916_CR20","doi-asserted-by":"publisher","first-page":"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), 1\u201318 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"916_CR21","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.H.: Optimal algorithms for approximate clustering. In: Proceedings of the 20th ACM Symposium on Theory of Computing (STOC), pp. 434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"issue":"3","key":"916_CR22","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. Inform. Process. Lett. 12(3), 133\u2013137 (1981)","journal-title":"Inform. Process. Lett."},{"key":"916_CR23","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."},{"issue":"4","key":"916_CR24","doi-asserted-by":"publisher","first-page":"998","DOI":"10.1287\/moor.2014.0652","volume":"39","author":"A Gupta","year":"2014","unstructured":"Gupta, A., Nagarajan, V.: Approximating sparse covering integer programs online. Math. Oper. Res. 39(4), 998\u20131011 (2014)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"916_CR25","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":"916_CR26","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."},{"key":"916_CR27","unstructured":"Liaw, C., Liu, P., Reiss, R.: Approximation schemes for covering and packing in the streaming model. In: Proceedings of the 30th Canadian Conference on Computational Geometry (CCCG), Winnipeg, MB, pp.\u00a0172\u2013179 (2018)"},{"issue":"1","key":"916_CR28","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."},{"key":"916_CR29","volume-title":"Approximation Algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, New York (2001)"},{"key":"916_CR30","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":"4","key":"916_CR31","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":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00916-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00916-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00916-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T05:03:22Z","timestamp":1651122202000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00916-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,6]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["916"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00916-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,6]]},"assertion":[{"value":"21 July 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 December 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}