  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 \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. Moreover, we
present a simple randomized O(\log n)-competitive algorithm, and a
deterministic O(\log\log n)-competitive algorithm for the fractional version of
the problem.
