Competitive Online Clustering with Movement Cost

1 Introduction

• The problem charges both movement between center configurations and the clustering cost for each request batch, while prior guarantees covered only k ≤ 2 on the line with k-median costs.The centers are chosen after each request multiset is observed.Source: §1 · pp. 2–3

1.1 Our Results and Techniques

• Randomized O(k)-competitiveness holds for norm-of-distances clustering on general metrics against adaptive online adversaries, and the bound is tight.The result generalizes earlier guarantees limited to k ≤ 2 on the line with k-median costs.Source: §1.1 · p. 3
• A Poissonization-based reduction converts each request batch into independent Poisson arrivals at request locations, with rates driven by requests’ current contributions to clustering cost.The resulting k-server process supplies configurations that the clustering algorithm follows.Source: §1.1 · p. 4
• Deterministic O(k)-competitive algorithms are also given on the line for norm-of-distances and, with symmetric norms, norm-of-radii objectives.For norm-of-radii, the analysis controls overlapping farthest requests by using line geometry and norm convexity and symmetry.Source: §1.1 · p. 5

1.2 Related Work

• The paper distinguishes movement-cost clustering from online learning with free movement and from consistent clustering, where movement is free or restricted by change limits.Its benchmark is an offline algorithm that may move centers while paying movement costs.Source: §1.2 · p. 5

• A configuration is a multiset of k points, and d(u,S) denotes the distance from u to its nearest point in S.Source: §2 · p. 6
• A norm is monotone when coordinatewise increases in nonnegative vectors cannot decrease its value, and symmetric when coordinate permutations leave its value unchanged.Source: §2 · p. 7
• A dual-norm unit vector attaining the norm through its inner product with a vector is called a norming functional.Source: §2 · p. 7
• Norm-of-distances costs apply a monotone norm to request-to-nearest-center distances, while norm-of-radii costs apply a symmetric, monotone norm to cluster radii.The former includes k-median, k-center, and the square root of k-means objectives; the latter includes sum-k-radii and k-center.Source: §2 · p. 7
• A randomized algorithm is α-competitive when its expected cost is at most α times the adversary’s expected cost plus a sequence-independent constant.The adversary may adapt to the randomized algorithm, so its cost can also be random.Source: §2 · p. 7

3.1 Warm-Up: The k-Center Objective

• A deterministic α-competitive k-server algorithm yields a deterministic O(α)-competitive CMC algorithm for the k-center objective by serving each batch’s farthest request.Using the k-competitive Work Function Algorithm gives a deterministic O(k)-competitive algorithm.Source: §3.1 · pp. 8–9

3.2 The Main Algorithm

• Norming-functional coordinates become Poisson arrival rates for shadow requests, and the CMC algorithm selects the least-cost configuration visited during each round.The online clustering cost is bounded by expected k-server movement, while the offline k-server cost is bounded by twice the offline CMC cost.Source: §3.2 · pp. 9–11
• O(k)-competitive randomized CMC follows by applying the k-competitive Work Function Algorithm to the ShadowServe reduction, which preserves competitiveness up to a constant factor against adaptive online adversaries.The reduction generates shadow requests at rates determined by a norming functional of the current distance vector.Source: §3.2 · pp. 9, 10, 12
• The reduction does not directly apply to k-server algorithms competitive only against oblivious adversaries, except when constant norming-functional rates make the shadow-request stream independent of the algorithm.Weighted ℓ1 norms have constant rates, so the reduction also applies to oblivious-adversary algorithms in that case.Source: §3.2 · p. 12

3.3 Generalization to Chasing Problems

• A batched F-chasing reduction yields an O(d)-competitive deterministic algorithm for batched convex body chasing and randomized guarantees for batched small set chasing.For small set chasing, the adaptive-adversary guarantee is O(2^w), while weighted ℓ1 yields O(w^2) against oblivious adversaries.Source: §3.3 · p. 13

4 Deterministic Algorithms on the Line

• Deterministic O(k)-competitive algorithms cover both norm-of-distances and norm-of-radii objectives on the line, matching the Ω(k) lower bound.The lower bound is inherited from k-server.Source: §4 · p. 13

4.1 Norm-of-Distances Objective

• For norm-of-distances, the algorithm combines Double Coverage movements with speeds scaled by a norming functional to relate movement and clustering costs.This is presented as a derandomization of the prior section's ideas.Source: §4 · pp. 13–14

4.2 Norm-of-Radii Objective

• The norm-of-radii analysis addresses double-charging by using line geometry to limit overlapping charges and symmetry to redistribute them.Several online centers may charge their costs to the same offline center; the analysis limits the resulting overlap to a constant factor.Source: §4 · p. 13, §4.2 · p. 17
• RadAggrDC is O(k)-competitive on the line when the norm at every round is symmetric.The continuous algorithm is informal when a center has equally distant farthest requests; a finite implementation avoids this issue while retaining the asymptotic guarantee.Source: §4.2 · p. 17

5 Conclusion and Discussion

• A Poissonization-based reduction gives a randomized O(k)-competitive algorithm for norm-of-distances on general metrics, extending prior guarantees for k-median on the line when k ≤ 2.Its rates are driven by a time-evolving norming functional, and the reduction also extends to chasing problems.Source: §5 · p. 19
• On the line, deterministic O(k)-competitive algorithms cover both norm-of-distances and norm-of-radii objectives.Source: §5 · p. 19
• Extending deterministic guarantees beyond the line and handling asymmetric norm-of-radii objectives remain open directions.The latter challenge applies even on the line and appears to require fundamentally new ideas.Source: §5 · p. 19

A.1 Non-Monotone Norm Gives Unbounded Competitive Ratio

• The paper attributes the impossibility to non-monotonicity breaking convexity when the norm is composed with coordinatewise convex distance functions.Source: §A.1 · p. 25
• No competitive algorithm exists for single-center online clustering with non-monotone norms, even for randomized algorithms against oblivious adversaries on the line.Source: §A.1 · p. 25
• The proof simulates chasing unions of two intervals using a single-center clustering instance with a non-monotone norm.Any competitive clustering algorithm would imply a competitive algorithm for that chasing problem, which is ruled out by the cited result.Source: §A.1 · pp. 25–26

A.2 Non-Negative Norming Functionals

• Monotone norms admit non-negative norming functionals.The proof establishes the existence of a non-negative subgradient.Source: §A.2 · p. 26
• A subgradient z at x satisfies ∥z∥*=1 and ⟨z, x⟩=∥x∥.Source: §A.2 · p. 27
• The proof obtains the dual-norm equality because a subgradient maximizes ⟨z, x⟩ and could be scaled up if its dual norm were below one.Source: §A.2 · p. 27

B Reduction for Chasing Problems

• ShadowServe issues requests during each round’s infinitesimal intervals with probability z_F(u) du, where z(u) is a norming functional for the current distance vector.It follows the F-chasing algorithm’s location and generates requests at rates determined by the functional’s coordinates.Source: B Reduction for Chasing Problems · p. 27
• An α-competitive randomized F-chasing algorithm yields an O(α)-competitive randomized algorithm for batched F-chasing against adaptive online adversaries.For weighted ℓ1 norms, the reduction also applies against oblivious adversaries.Source: B Reduction for Chasing Problems · p. 27
• The reduction bounds ShadowServe’s movement by the F-chasing algorithm’s movement and its expected service cost by that algorithm’s expected movement cost.The adaptive adversary’s cost in F-chasing is bounded by the batched F-chasing adversary’s cost.Source: B Reduction for Chasing Problems · p. 28

B.1 Derandomizing Convex Body Chasing

• An α-competitive randomized algorithm for batched convex body chasing against an oblivious adversary implies an α-competitive deterministic algorithm.The deterministic algorithm outputs the expected randomized position each round, with cost no greater than the randomized algorithm’s expected cost.Source: §B.1 · p. 29
• The derandomization bounds movement and distance-to-body costs using convexity and Jensen’s inequality.The distance to each convex body is convex, and the batch norm is monotone and convex.Source: §B.1 · p. 29
• Theorem 3.10 follows by applying Theorem 1.3 to convex body chasing and then using the derandomization lemma.The lemma converts the randomized oblivious-adversary guarantee into a deterministic one.Source: §B.1 · pp. 29–30

C Discretized Implementation of Line Algorithms

• At each round’s end, the algorithm outputs the iteration-start configuration with the smallest clustering cost, while the next round begins from the final internal configuration.The 32k bound is not optimized; discretization error is absorbed by choosing sufficiently short segments relative to the current norm.Source: C Discretized Implementation of Line… · p. 30
• 32k-competitive is the guarantee for the discrete implementation of RadAggrDC.The method splits each round into short segments, freezes a farthest request and norming functional per starting cluster, and moves selected neighboring centers toward that request.Source: C Discretized Implementation of Line… · p. 30
• 8k-competitive is the guarantee for the discrete implementation of AggrDC.It processes requests in a fixed order, uses a norming functional for the starting distance vector, and doubles the potential to absorb the comparison error.Source: C Discretized Implementation of Line… · p. 32

D Associations for Norm-of-Radii Objective

• On the line, nearest-center assignment has norm-of-radii cost at most a constant factor above the minimum over assignments.The result applies to any monotone symmetric norm.Source: D Associations for Norm-of-Radii… · p. 32
• The line analysis uses left and right radii separately, whose norms together approximate the norm of the cluster-radius vector within a constant factor.A cluster radius is the maximum distance from its center to an assigned request; the optimal assignment can be taken uncrossed, with no cluster containing another center.Source: D Associations for Norm-of-Radii… · pp. 32–33
• On general metrics, nearest-center assignment can cost Θ(k) times the optimal assignment, and its cost is always O(k) times optimal.In the star instance, each request is closer to its leaf center, but assigning all requests to the hub gives the optimum and the ratio tends to k−1.Source: D Associations for Norm-of-Radii… · p. 34

E (A)symmetric Norm-of-Radii Objective

• Double Coverage preserves the relative order of centers, while the weighted example requires swapping them.The analysis of RadAggrDC needed symmetry to permute cost-vector coordinates; asymmetric norms therefore require something fundamentally different from Double Coverage.Source: E (A)symmetric Norm-of-Radii Objective · p. 34
• The example uses two centers and the asymmetric norm B·rad1 + rad2 on repeated requests at 0, 1, and B.The offline algorithm switches center locations so the cheap center serves {0, 1} and the expensive center serves B.Source: E (A)symmetric Norm-of-Radii Objective · p. 34
• Keeping the expensive center on the left costs at least Θ(B) in the example, yielding an unbounded competitive ratio.The alternative is for the cheap center to cluster {1, B}, which can be arbitrarily more expensive.Source: E (A)symmetric Norm-of-Radii Objective · p. 35