{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T19:25:53Z","timestamp":1777490753629,"version":"3.51.4"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,10,13]],"date-time":"2007-10-13T00:00:00Z","timestamp":1192233600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,10]]},"DOI":"10.1007\/s00224-007-9085-7","type":"journal-article","created":{"date-parts":[[2007,10,12]],"date-time":"2007-10-12T15:32:15Z","timestamp":1192203135000},"page":"486-496","source":"Crossref","is-referenced-by-count":23,"title":["A Randomized Algorithm for Online Unit Clustering"],"prefix":"10.1007","volume":"45","author":[{"given":"Timothy M.","family":"Chan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hamid","family":"Zarrabi-Zadeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,10,13]]},"reference":[{"key":"9085_CR1","doi-asserted-by":"crossref","unstructured":"Adamy, U., Erlebach, T.: Online coloring of intervals with bandwidth. In: Proc. 1st Workshop Approx. Online Algorithms. Lecture Notes in Computer Science, vol.\u00a02909, pp.\u00a01\u201312 (2003)","DOI":"10.1007\/978-3-540-24592-6_1"},{"key":"9085_CR2","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0925-7721(98)00028-5","volume":"11","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., van Kreveld, M., Suri, S.: Label placement by maximum independent set in rectangles. Comput. Geom. Theory Appl. 11, 209\u2013218 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9085_CR3","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"T.M. Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46, 178\u2013189 (2003)","journal-title":"J. Algorithms"},{"key":"9085_CR4","doi-asserted-by":"crossref","unstructured":"Charikar, M., O\u2019Callaghan, L., Panigrahy, R.: Better streaming algorithms for clustering problems. In: Proc. 35th ACM Sympos. Theory Comput., pp.\u00a030\u201339 (2003)","DOI":"10.1145\/780542.780548"},{"issue":"6","key":"9085_CR5","doi-asserted-by":"crossref","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":"9085_CR6","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, Cambridge (2001)","edition":"2"},{"key":"9085_CR7","doi-asserted-by":"crossref","unstructured":"Epstein, L., Levy, M.: Online interval coloring and variants. In: Proc. 32nd International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol.\u00a03580, pp.\u00a0602\u2013613 (2005)","DOI":"10.1007\/11523468_49"},{"key":"9085_CR8","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1137\/S0097539702402676","volume":"34","author":"T. Erlebach","year":"2005","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time approximation schemes for geometric intersection graphs. SIAM J. Comput. 34, 1302\u20131323 (2005)","journal-title":"SIAM J. Comput."},{"key":"9085_CR9","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.H.: Optimal algorithms for approximate clustering. In: Proc. 20th ACM Sympos. Theory Comput., pp.\u00a0434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"issue":"3","key":"9085_CR10","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R.J. Fowler","year":"1981","unstructured":"Fowler, R.J., Paterson, M.S., 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":"9085_CR11","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T. Gonzalez","year":"1985","unstructured":"Gonzalez, T.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"9085_CR12","doi-asserted-by":"crossref","unstructured":"Guha, S., Mishra, N., Motwani, R., O\u2019Callaghan, L.: Clustering data streams. In: Proc. 41st IEEE Sympos. Found. Comput. Sci., pp.\u00a0359\u2013366 (2000)","DOI":"10.1109\/SFCS.2000.892124"},{"key":"9085_CR13","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1002\/jgt.3190120212","volume":"12","author":"A. Gy\u00e1rf\u00e1s","year":"1988","unstructured":"Gy\u00e1rf\u00e1s, A., Lehel, J.: On-line and first-fit colorings of graphs. J. Graph Theory 12, 217\u2013227 (1988)","journal-title":"J. Graph Theory"},{"key":"9085_CR14","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"D.S. Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maas, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32, 130\u2013136 (1985)","journal-title":"J. ACM"},{"key":"9085_CR15","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0012-365X(94)00285-Q","volume":"8","author":"H.A. Kierstead","year":"1995","unstructured":"Kierstead, H.A., Qin, J.: Coloring interval graphs with First-Fit. SIAM J. Discrete Math. 8, 47\u201357 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"9085_CR16","first-page":"143","volume":"33","author":"H.A. Kierstead","year":"1981","unstructured":"Kierstead, H.A., Trotter, W.A.: An extremal problem in recursive combinatorics. Congr. Numer. 33, 143\u2013153 (1981)","journal-title":"Congr. Numer."},{"key":"9085_CR17","unstructured":"Lipton, R.J., Tomkins, A.: Online interval scheduling. In: Proc. 5th Sympos. Discrete Algorithms, pp.\u00a0302\u2013311 (1994)"},{"key":"9085_CR18","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"M.V. Marathe","year":"1995","unstructured":"Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple heuristics for unit disk graphs. Networks 25, 59\u201368 (1995)","journal-title":"Networks"},{"issue":"1","key":"9085_CR19","doi-asserted-by":"crossref","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."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9085-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9085-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9085-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:35Z","timestamp":1558698695000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9085-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,13]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["9085"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9085-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,13]]}}}