A randomized algorithm for online unit clustering

DOI10.1007/S00224-007-9085-7MaRDI QIDQ839627zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan, Hamid Zarrabi-Zadeh

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

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

Recommendations

• A Randomized Algorithm for Online Unit Clustering
• An Improved Algorithm for Online Unit Clustering
• An improved algorithm for online unit clustering
• Better bounds on online unit clustering
• On the Online Unit Clustering Problem

Cites work

• scientific article; zbMATH DE number 1003261 (Why is no real title available?)
• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• Approximation and Online Algorithms
• Approximation schemes for covering and packing problems in image processing and VLSI
• Automata, Languages and Programming
• Better streaming algorithms for clustering problems
• Clustering to minimize the maximum intercluster distance
• Incremental Clustering and Dynamic Information Retrieval
• Introduction to algorithms
• Label placement by maximum independent set in rectangles
• On the Complexity of Some Common Geometric Location Problems
• On-Line and First-fit Coloring of Graphs that Do Not Induce $P_5 $
• On-line and first fit colorings of graphs
• Optimal packing and covering in the plane are NP-complete
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Polynomial-time approximation schemes for packing and piercing fat objects
• Simple heuristics for unit disk graphs

Cited in

(17)

• Online sum-radii clustering
• Online coloring a token graph
• An improved algorithm for online unit clustering
• An improved lower bound for one-dimensional online unit clustering
• Online unit clustering and unit covering in higher dimensions
• Online weight balancing on the unit circle
• A new model for the linear 1-dimensional online clustering problem
• Online class cover problem
• Online geometric covering and piercing
• Online unit clustering in higher dimensions
• An online 2-dimensional clustering problem with variable sized clusters
• A competitive strategy for distance-aware online shape allocation
• An Improved Algorithm for Online Unit Clustering
• Better bounds on online unit clustering
• Online unit clustering: Variations on a theme
• Online clustering with variable sized clusters
• A Randomized Algorithm for Online Unit Clustering

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q839627)