A randomized algorithm for online unit clustering

DOI10.1007/s00224-007-9085-7zbMath1187.68701OpenAlexW1976011284MaRDI QIDQ839627

Hamid Zarrabi-Zadeh, Timothy M. Chan

Publication date: 2 September 2009

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-007-9085-7

zbMATH Keywords

online algorithmsrandomized algorithmsunit clustering

Mathematics Subject Classification ID

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

Related Items (8)

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 ⋮ Online sum-radii clustering ⋮ An improved lower bound for one-dimensional online unit clustering ⋮ Online unit covering in Euclidean space ⋮ Online coloring a token graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clustering to minimize the maximum intercluster distance
• Optimal packing and covering in the plane are NP-complete
• Label placement by maximum independent set in rectangles
• On the Complexity of Some Common Geometric Location Problems
• Better streaming algorithms for clustering problems
• 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
• Simple heuristics for unit disk graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Automata, Languages and Programming
• Approximation and Online Algorithms

This page was built for publication: A randomized algorithm for online unit clustering