Online Sum-Radii Clustering

Details Online Sum-Radii Clustering Online Sum-Radii Clustering

2011-09-25

arxiv.org/abs/1109.5325v1

Computer Science

Data Structures and Algorithms

Scientific paper

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 metric spaces other than the line is $\Theta(\log n)$, where the upper bound follows from a primal-dual algorithm and holds for general metric spaces, 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 metric spaces induced by 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 $\Omega(\log\log n)$ on the randomized competitive ratio of Online Sum-Radii Clustering in tree metrics, and a randomized $O(2^d \sqrt{d}\,\log\log n)$-competitive algorithm for the $d$-dimensional Euclidean space. Moreover, we present a simple and memoryless randomized $O(\log n)$-competitive algorithm and a deterministic $O(\log\log n)$-competitive fractional algorithm, which both work for general metric spaces.

Affiliated with

Also associated with

No associations

Rating

Online Sum-Radii Clustering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Online Sum-Radii Clustering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Online Sum-Radii Clustering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-74061