Paper Info
Title
Online Sum-Radii Clustering.
Abstract
In Online Sum-Radii Clustering, n demand points arrive online and must be irrevocably assigned to a cluster upon arrival. The cost of each cluster is the sum of a fixed opening cost and its radius, and the objective is to minimize the total cost of the clusters opened by the algorithm. We show that the deterministic competitive ratio of Online Sum-Radii Clustering for general metric spaces is Θ(logn), where the upper bound follows from a primal-dual online algorithm, and the lower bound is valid for ternary Hierarchically Well-Separated Trees (HSTs) and for the Euclidean plane. Combined with the results of (Csirik et al., MFCS 2010), this result demonstrates that the deterministic competitive ratio of Online Sum-Radii Clustering changes abruptly, from constant to logarithmic, when we move from the line to the plane. We also show that Online Sum-Radii Clustering in HSTs is closely related to the Parking Permit problem introduced by (Meyerson, FOCS 2005). Exploiting the relation to Parking Permit, we obtain a lower bound of Ω(loglogn) on the randomized competitive ratio of Online Sum-Radii Clustering in tree metrics. Moreover, we present a simple randomized O(logn)-competitive algorithm, and a deterministic O(loglogn)-competitive algorithm for the fractional version of the problem.
Year
DOI
Venue
2011
10.1007/978-3-642-32589-2_36
Theoretical Computer Science
Keywords
DocType
Volume
competitive algorithm,euclidean plane,randomized competitive ratio,deterministic o,deterministic competitive ratio,online sum-radii clustering change,online sum-radii clustering,total cost,fixed opening cost,primal-dual online algorithm,lower bound,euclidean space,competitive ratio,data structure,metric space,upper bound
Journal
540
ISSN
Citations 
PageRank 
0304-3975
1
0.35
References 
Authors
17
2
Name
Order
Citations
PageRank
Dimitris Fotakis157059.07
Paraschos Koutris234726.63