{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T12:42:29Z","timestamp":1763642549234,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,12,15]],"date-time":"2018-12-15T00:00:00Z","timestamp":1544832000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2018,12,15]]},"abstract":"<jats:p>This column is devoted to geometric clustering and covering problems in Rd. As exact solutions for these problems are usually out of reach (unless d = 1), one is forced to deal with approximations. Here we mostly consider online algorithms, as the online setting introduces additional difficulty due to uncertainty about the future. One representative problem is the following (so-called Unit Covering): given a set of n points in Rd, cover the points by balls of unit diameter, so as to minimize the number of balls used.<\/jats:p>","DOI":"10.1145\/3300150.3300161","type":"journal-article","created":{"date-parts":[[2018,12,17]],"date-time":"2018-12-17T13:17:16Z","timestamp":1545052636000},"page":"46-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Computational Geometry Column 68"],"prefix":"10.1145","volume":"49","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[{"name":"University of Wisconsin-Milwaukee, Milwaukee, WI, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,12,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2016.04.002"},{"key":"e_1_2_1_2_1","first-page":"345","volume-title":"Ap- proximation Algorithms for NP-hard Problems","author":"Bern Marshall","year":"1997"},{"volume-title":"Online Computation and Competitive Analysis","year":"1998","author":"Borodin Allan","key":"e_1_2_1_3_1"},{"volume-title":"Research Problems in Discrete Geometry","year":"2005","author":"Brass Peter","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9085-7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702418498"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412700.1412719"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9586-2"},{"issue":"4","key":"e_1_2_1_9_1","first-page":"593","article-title":"clustering problem with variable sized clusters","volume":"14","author":"ad Imreh Gabriella","year":"2013","journal-title":"Optim. Eng."},{"key":"e_1_2_1_10_1","first-page":"252","volume-title":"Proc. 15th International Workshop on Approximation and Online Algorithms (WAOA), LNCS 10787","author":"Dumitrescu Adrian","year":"2017"},{"volume-title":"Proc. 12th Annual International Conference on Combinatorial Optimization and Appli- cations (COCOA 2018","year":"2018","author":"Dumitrescu Adrian","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.07.008"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.04.046"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868245"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62255"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"e_1_2_1_17_1","first-page":"306","article-title":"Gonzalez, Clustering to minimize the maximum intercluster distance, Theoret. Com- put","volume":"38","author":"Teo","year":"1985","journal-title":"Sci."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214106"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.2.180"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.06.055"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213014"},{"volume-title":"Approximation Algorithms","year":"2001","author":"Vazirani Vijay","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms, Cam- bridge University Press","author":"Williamson David P.","year":"2011"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9208-9"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3300150.3300161","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3300150.3300161","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:22Z","timestamp":1750206322000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3300150.3300161"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,15]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,15]]}},"alternative-id":["10.1145\/3300150.3300161"],"URL":"https:\/\/doi.org\/10.1145\/3300150.3300161","relation":{},"ISSN":["0163-5700"],"issn-type":[{"type":"print","value":"0163-5700"}],"subject":[],"published":{"date-parts":[[2018,12,15]]},"assertion":[{"value":"2018-12-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}