An improved algorithm for online unit clustering

DOI10.1007/s00453-008-9208-9zbMath1185.68863OpenAlexW2066449891MaRDI QIDQ1040649

Timothy M. Chan, Hamid Zarrabi-Zadeh

Publication date: 25 November 2009

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9208-9

zbMATH Keywords

online algorithmsrandomized algorithmsunit clustering

Mathematics Subject Classification ID

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items

Online unit clustering and unit covering in higher dimensions, Better bounds on online unit clustering, An online 2-dimensional clustering problem with variable sized clusters, Online clustering with variable sized clusters, An improved lower bound for one-dimensional online unit clustering, Online unit covering in Euclidean space

Cites Work

• Unnamed Item
• Optimal packing and covering in the plane are NP-complete
• Covering a set of points in multidimensional space
• Fast stabbing of boxes in high dimensions
• Approximation schemes for covering and packing problems in image processing and VLSI
• On-line and first fit colorings of graphs
• Incremental Clustering and Dynamic Information Retrieval
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• Profit-earning facility location
• On the Online Unit Clustering Problem
• A Randomized Algorithm for Online Unit Clustering
• Algorithms – ESA 2004