Online unit clustering: Variations on a theme

DOI10.1016/j.tcs.2008.04.046zbMath1152.68060OpenAlexW2095128928MaRDI QIDQ954982

Asaf Levin, Rob van Stee, Leah Epstein

Publication date: 18 November 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.04.046

zbMATH Keywords

clusteringonline algorithmscoloring

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Clustering in the social and behavioral sciences (91C20) Pattern recognition, speech recognition (68T10)

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 ⋮ Analysis of a first-fit algorithm for the capacitated unit covering problem ⋮ On capacitated covering with unit balls

Cites Work

• Unnamed Item
• Unnamed Item
• An on-line graph coloring algorithm with sublinear performance ratio
• Algorithms for on-line bin-packing problems with cardinality constraints
• Bin packing problems with rejection penalties and their dual problems
• An Improved Algorithm for Online Unit Clustering
• Dynamic Bin Packing
• On-line and first fit colorings of graphs
• On-line routing of virtual circuits with applications to load balancing and machine scheduling
• Speed is as powerful as clairvoyance
• Capacitated vertex covering
• Incremental Clustering and Dynamic Information Retrieval
• On-Line Load Balancing of Temporary Tasks on Identical Machines
• A General Approximation Technique for Constrained Forest Problems
• Multiprocessor Scheduling with Rejection
• Online Bin Packing with Cardinality Constraints
• On the Max Coloring Problem
• On the Online Unit Clustering Problem
• A Randomized Algorithm for Online Unit Clustering
• Bin Packing with Rejection Revisited
• Graph Coloring with Rejection
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques