Online sum-radii clustering

DOI10.1016/j.tcs.2013.03.010zbMath1359.68325arXiv1109.5325WikidataQ59818391 ScholiaQ59818391MaRDI QIDQ2453160

Paraschos Koutris, Dimitris Fotakis

Publication date: 6 June 2014

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

Full work available at URL: https://arxiv.org/abs/1109.5325

zbMATH Keywords

competitive analysisonline algorithmssum-\(k\)-radii clustering

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W27: Online algorithms; streaming algorithms

Related Items

An online 2-dimensional clustering problem with variable sized clusters, An incremental version of the \(k\)-center problem on boundary of a convex polygon

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph clustering
• A randomized algorithm for online unit clustering
• On metric clustering to minimize the sum of radii
• Clustering to minimize the sum of cluster diameters
• Online clustering with variable sized clusters
• On the competitive ratio for online facility location
• Polynomial time approximation schemes for base station coverage with minimum total radii
• A general approach to online network optimization problems
• On the online unit clustering problem
• The Online Set Cover Problem
• Better Bounds on Online Unit Clustering
• Incremental Clustering and Dynamic Information Retrieval
• Algorithms – ESA 2005