{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:31Z","timestamp":1759638151456,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319894409"},{"type":"electronic","value":"9783319894416"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","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-319-89441-6_18","type":"book-chapter","created":{"date-parts":[[2018,3,30]],"date-time":"2018-03-30T09:43:23Z","timestamp":1522403003000},"page":"238-252","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Online Unit Clustering in Higher Dimensions"],"prefix":"10.1007","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,31]]},"reference":[{"issue":"2","key":"18_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":"18_CR2","doi-asserted-by":"crossref","unstructured":"Azar, Y., Buchbinder, N., Hubert Chan, T.-H., Chen, S., Cohen, I.R., Gupta, A., Huang, Z., Kang, N., Nagarajan, V., Naor, J., Panigrahi, D.: Online algorithms for covering and packing problems with convex objectives. In: Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 148\u2013157. IEEE (2016)","DOI":"10.1109\/FOCS.2016.24"},{"key":"18_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. 85\u2013100. SIAM (2013)","DOI":"10.1137\/1.9781611973105.6"},{"key":"18_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. 1038\u20131050. SIAM (2017)","DOI":"10.1137\/1.9781611974782.66"},{"key":"18_CR5","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)"},{"issue":"2","key":"18_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":"18_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":"18_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."},{"issue":"3","key":"18_CR9","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":"18_CR10","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":"18_CR11","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. Optim. Eng. 14(4), 575\u2013593 (2013)","journal-title":"Optim. Eng."},{"key":"18_CR12","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), p. 159. IEEE (2014)","DOI":"10.1109\/CINTI.2014.7028668"},{"key":"18_CR13","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":"18_CR14","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":"18_CR15","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":"18_CR16","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.H.: Optimal algorithms for approximate clustering. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pp. 434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"issue":"3","key":"18_CR17","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":"18_CR18","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":"18_CR19","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":"18_CR20","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":"18_CR21","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":"1","key":"18_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."},{"key":"18_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, New York (2001). https:\/\/doi.org\/10.1007\/978-3-662-04565-7"},{"key":"18_CR24","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":"18_CR25","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","Approximation and Online Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-89441-6_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T12:20:32Z","timestamp":1710246032000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-89441-6_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319894409","9783319894416"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-89441-6_18","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":"31 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WAOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Approximation and Online Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vienna","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 September 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 September 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"waoa2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/algo2017.ac.tuwien.ac.at\/waoa","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}