PaperlayerView exact revision on arXiv

Source-linked AI summary

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, Justin Ward

arXiv:1612.07925v2cs.DS

TL;DR

General k-means lacks a strong unrestricted guarantee: local search provides 9-plus-epsilon, and its hard at-most-k constraint complicates approximation. The paper develops a primal-dual approach exploiting Euclidean geometry while preserving the facility bound, achieving 6.357-plus-epsilon for k-means and improved guarantees for related variants.

  • Problem

    Unrestricted k-means has a 9-plus-epsilon local-search guarantee, while enforcing the hard constraint of selecting at most k clusters remains a central challenge.

  • Method

    The paper combines Euclidean-geometry-based LMP approximation with a new primal-dual algorithm that opens exactly k facilities with only an arbitrarily small loss.

  • Results

    6.357-plus-epsilon approximation is obtained for Euclidean k-means, alongside 2.633-plus-epsilon for Euclidean k-median and 9-plus-epsilon for general-metric k-means.

  • Takeaways & Limitations

    The techniques narrow the gap between known upper and lower bounds and extend beyond Euclidean k-means to general-metric k-means and Euclidean k-median.

  • Takeaways & Limitations

    The paper leaves open whether stronger LMP algorithms can be combined with its lossless rounding to obtain a 2-plus-epsilon approximation for k-median.

Abstract

from arXiv · show

Clustering is a classic topic in optimization with $k$-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algorithm for $k$-means with a provable guarantee is a simple local search heuristic yielding an approximation guarantee of $9+ε$, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that allows us to (1) exploit the geometric structure of $k$-means and (2) to satisfy the hard constraint that at most $k$ clusters are selected without deteriorating the approximation guarantee. Our main result is a $6.357$-approximation algorithm with respect to the standard LP relaxation. Our techniques are quite general and we also show improved guarantees for the general version of $k$-means where the underlying metric is not required to be Euclidean and for $k$-median in Euclidean metrics.

1 Introduction

The paper develops primal-dual techniques that exploit Euclidean geometry and enforce the at-most-k-cluster constraint, improving guarantees for k-means and related problems. It obtains a 6.357-plus-epsilon approximation for Euclidean k-means and improved guarantees for general-metric k-means and Euclidean k-median.

  • Main results: The algorithm works when k and the dimension are part of the input, without assumptions on the dataset.
  • Main results: 6.357-plus-epsilon approximation is achieved for k-means, with the standard LP integrality gap at most 6.357.The guarantee applies for every epsilon > 0.
  • Technical contributions: The approach combines an improved LMP approximation based on Euclidean geometry with a primal-dual algorithm that opens exactly k facilities.
  • Technical contributions: The new rounding procedure reduces the facility-opening loss from 2 to 1-plus-epsilon by constructing and combining consecutive solutions with close opening costs and dual values.
  • Extensions to other problems: 2.633-plus-epsilon approximation is obtained for Euclidean k-median, with the standard LP integrality gap at most 2.633.
  • Extensions to other problems: 9-plus-epsilon approximation is obtained for k-means in general metrics, with the standard LP integrality gap at most 9.
  • Extensions to other problems: The general-metric k-means extension is hard to approximate within approximately 3.94, expressed as 1 + 8/e − epsilon.

2 The standard LP relaxation and its Lagrangian relaxation

The standard LP relaxation models facility opening and client assignment with fractional variables, while its at-most-k constraint creates the main approximation difficulty. Lagrangian relaxation moves that constraint into the objective, enabling facility-location-style primal-dual methods and LMP guarantees.

  • The standard LP relaxation: The standard LP uses y_i for facility opening and x_ij for assigning client j to facility i.
  • The standard LP relaxation: Its constraints require every client to connect, permit connections only to opened facilities, and limit opened facilities to at most k.
  • The standard LP relaxation: The relaxation allows nonnegative fractional x and y variables instead of Boolean decisions.
  • Lagrangian relaxation: The hard at-most-k constraint is moved into the objective by multiplying it by a Lagrange multiplier lambda.
  • Lagrangian relaxation: With uniform opening cost lambda, the Lagrangian relaxation and dual become facility-location formulations when the constant lambda times k is ignored.
  • LMP approximations: An LMP rho-approximation yields a rho-factor bound relative to the standard LP when lambda is zero or the returned solution opens at most k facilities.

3 Exploiting Euclidean metrics via primal-dual algorithms

The parameterized JV(δ) primal-dual algorithm exploits Euclidean structure through a more aggressive facility-opening strategy, while its pruning phase selects facilities from a conflict graph. Optimizing δ yields improved guarantees for Euclidean k-means and k-median, and the resulting LMP guarantees also bound standard-LP integrality gaps.

  • Algorithmic approach: JV(δ) modifies the Jain–Vazirani algorithm by using δ to regulate the aggressiveness of facility opening; smaller δ produces a more aggressive strategy.The modification adds a distance condition to conflict-graph edges, reducing edges and tending to enlarge the maximal independent set.
  • Algorithmic approach: The algorithm first grows a feasible dual solution by increasing active clients’ dual variables until facilities or client-facility edges become tight, then removes affected clients.Facilities with tight constraints become witnesses for removed clients, and feasibility is maintained because tight constraints no longer increase afterward.
  • Algorithmic approach: The pruning phase builds a client-facility graph and conflict graph, finds a maximal independent set of facilities, and connects clients to their closest selected facility.Conflict-graph edges encode shared clients together with the δ-scaled facility-distance condition.
  • k-Means objective in general metrics: For general-metric k-means, setting δ = ∞ recovers JV, whose analysis bounds the connection cost through the standard 3-hop case.The Euclidean analysis exploits slack in this bound to permit more aggressive opening.
  • k-Means objective in Euclidean metrics: 6.3574 is the Euclidean k-means approximation guarantee obtained by choosing δmean ≈2.3146, with the same value bounding the standard-LP integrality gap.The guarantee is established using properties of squared distances in Euclidean metrics.
  • k-Median objective in Euclidean metrics: 2.633 is the Euclidean k-median approximation guarantee, obtained with δmed ≈1.633, and it also bounds the standard-LP integrality gap.The analysis optimizes δ separately for the k-median objective.

4 Quasi-polynomial time algorithm

The quasi-polynomial algorithm converts LMP primal-dual solutions into solutions obeying the at-most-k facility constraint, while preserving the approximation guarantee up to an arbitrarily small loss.

  • Overview: A discretization step restricts centers to a finite candidate set, incurring an arbitrarily small approximation loss.The resulting discrete problem supports facility-location-style linear programming and primal-dual methods.
  • Generating close solutions: The algorithm generates a sequence of good dual solutions for increasing facility-opening prices, with consecutive solutions kept close.Each α(ℓ) is feasible for DUAL(ℓ·εz), and the construction uses bucketed client dual values to maintain witness relationships.
  • QuasiSweep: QuasiSweep raises active clients’ dual values while decreasing larger values, stopping clients when tight facilities provide witnesses.The resulting solution remains feasible, and every client has a witness satisfying the bucket invariant.
  • Finding a solution of size k: QuasiGraphUpdate interpolates between consecutive conflict graphs so maximal independent sets lose at most one facility per step.This controlled interpolation guarantees that an intermediate independent set has exactly k facilities.
  • Guarantee and runtime: The resulting algorithm runs in n^O(ε^-1 log n) time and produces a (ρ + O(ε))-approximate solution.The same quasi-polynomial framework extends to the other considered objectives, with adjusted parameters and non-squared distances for k-median.

5 Polynomial time algorithm

The polynomial-time algorithm combines geometric LMP improvements with a primal-dual rounding procedure that raises facility prices and reaches exactly k open facilities while preserving the approximation guarantee up to ε.

  • δmean ≈2.3146 and ρmean = (1 + δmean)^2 ≈6.3574 parameterize the k-means approximation analysis.
  • The algorithm permits facility-specific prices in {λ, λ + εz} and treats facilities as tight when their prices are paid in the dual.Special facilities may also be opened without being tight, with designated special clients paying for them.
  • RaisePrice increases one facility’s price and produces a close sequence of λ-roundable solutions, while GraphUpdate interpolates between consecutive solutions.The polynomial-time construction relaxes some requirements of good solutions and uses sequences with polynomial length.
  • GraphUpdate maintains integral solutions whose number of open facilities decreases by at most one, so the sequence contains a solution with exactly k facilities.The algorithm begins with all facilities and eventually reaches one, guaranteeing an intermediate size k.
  • The resulting method runs in polynomial time and yields a (ρ + ε)-approximation algorithm for k-means.The analysis establishes the stated polynomial-time guarantee through RaisePrice and GraphUpdate.

6 Opening a set of exactly k facilities in a close, roundable sequence

GraphUpdate combines two close roundable solutions through hybrid client-facility and conflict graphs, maintaining independent sets until one opens exactly k facilities with bounded connection cost.

  • Starting from a maximal independent set, GraphUpdate greedily extends and updates independent sets while their size decreases by at most one.This preserves the transition structure needed to reach an exact cardinality.
  • The conflict graph connects facilities sharing a client when their squared distance is at most δ times the smaller opening time.Maximal independent sets in this graph represent compatible opened-facility sets.
  • GraphUpdate forms a hybrid client-facility graph by combining the two consecutive solution graphs and duplicating facilities when necessary.The corresponding conflict graphs use shared clients and opening times from the two solutions.
  • GraphUpdate runs in polynomial time because it performs polynomially many steps, each constructing a conflict graph and maintaining a maximal independent set greedily.
  • Any constructed independent set with at least k facilities has connection cost bounded by (ρ + O(ε))OPT_k.The initial set has connection cost at most OPT_k, and the same type of bound is proved for later sets.
  • The main result bounds the connection cost of GraphUpdate’s independent sets in terms of OPT_k, yielding the theorem for the polynomial-time algorithm.Theorem 6.4 supplies the approximation bound used in the final result.

7 The algorithm RaisePrice

RaisePrice incrementally increases facility prices while repairing dual solutions through thresholded sweeps, producing polynomially many close roundable solutions despite allowing some clients to become undecided.

  • The algorithm classifies clients as witnessed, stopped, or undecided according to tight facilities, nearby clients, and the absence of either condition.A stopped client is separated from its stopper by a factor satisfying αj ≥ 9αj′.
  • Lemma 7.1 shows that every stopped client is ultimately stopped by a client that is not stopped.The proof uses induction over non-decreasing α-values and the triangle inequality.
  • RaisePrice starts from a λ-roundable, completely decided dual solution and increases a selected facility’s price by εz.Its output is a sequence of close λ-roundable solutions whose final solution has all clients decided.
  • Sweep uses thresholds θs with K = Θ(ε^-1γ^-4) and a random shift so each stage changes only a constant number of α-value buckets.This bounds total value changes by n^O(K) and enables polynomial running time, at the cost of some undecided clients.
  • Only an arbitrarily small fraction of clients can become bad, and their service-cost contribution can be bounded by O(ε)·OPT_k.The analysis uses threshold selection and special facilities to handle dense clients.
  • The procedure’s central difficulty is handling clients that become undecided or use most of their dual values to pay facility-opening costs.Special facilities and special-client sets address the latter case.

8 Analysis of the polynomial-time algorithm

The polynomial-time analysis shows that decided clients satisfy the roundability conditions, while the remaining undecided clients form a controlled exception whose cost is bounded through threshold and density arguments.

  • A solution with no undecided clients is roundable with no special facilities or bad clients.Witnessed clients have tight facilities, and stopped clients are ultimately stopped by witnessed clients.
  • The analysis characterizes when clients become undecided by studying Sweep, invariants, and the threshold stages of RaisePrice.
  • Only an arbitrarily small constant fraction of clients lacks the desired guarantee, and their contribution to OPT_k is bounded through service-cost and density arguments.Dense clients require the special-facility and special-client construction.

8.1 Basic properties of Sweep and Invariants 2, 3, and 4

The algorithm maintains feasible dual solutions satisfying four invariants while Sweep regulates client α-values through witness, stopping, and monotonicity rules.

  • Invariants: Lemma 8.1 establishes that Invariants 2, 3, and 4 hold throughout Algorithm 1.Invariant 2 includes dual feasibility and α_j ≥ 1; Invariant 3 prevents strict α-ball containment, and Invariant 4 ensures every client is decided initially.
  • Initialization: The initialization procedure constructs a feasible solution with every client’s α-value at least 1.The lower bound follows from stopping at a facility edge and the preprocessing guarantee on squared distances.
  • Sweep properties: Sweep keeps clients decided during a call once they acquire a witness or are stopped.Witnesses remain tight, while stopped clients retain their stopping relation until Sweep ends.
  • Sweep properties: If one client’s α-ball contains another decided client’s α-ball, the containing client is also decided.The proof transfers either the witness relation or the stopping relation between the two clients.
  • Sweep properties: Sweep does not increase α-values below the minimum undecided value or decrease values whose bucket is no larger than that minimum’s bucket.This monotonicity property controls which clients can change during a Sweep call.

8.2 Characterizing currently undecided clients

The analysis characterizes undecided clients across RaisePrice stages, showing that their α-values cannot fall below stage thresholds and that initially exceptional clients become decided early.

  • Stage 1: Stage 1 uses only one Sweep call, after which every client initially undecided has α_j no greater than its initial value.This bounds the first-stage evolution of clients in U(0).
  • Later stages: For every solution produced by RaisePrice, an undecided client j satisfies α_j ≥ α_j^(0).The proof rules out violations by considering each Sweep removal rule and the persistence of decided status.
  • Later stages: In every stage s > 1, Sweep changes no α_j until θ reaches θ_{s−1}.Consequently, every client with α_j < θ_{s−1} remains decided in solutions produced during that stage.
  • Stage 1: Initially exceptional clients in U(0) become decided below θ_1.For each such client, α_j + εz remains below θ_1, and later stages leave its α-value unchanged.

8.3 Bounding the cost of clients

The section bounds client connection costs by associating clients with tight facilities, distinguishing regular clients from a potentially bad set B.

  • Potentially bad clients: The set B contains clients whose connection costs may exceed the target guarantee.Clients outside B satisfy the first inequality of Property 2, while clients in B satisfy only the weaker inequality.
  • Cost bounds: Clients outside B have a tight facility satisfying the stronger connection-cost inequality required by Property 2.The proof proceeds by induction over client α-values and handles witnessed, stopped, and undecided cases.
  • Cost bounds: Every client, including those in B, has a tight facility satisfying a weaker bound involving 6α_j^(0).This universal bound is the fallback guarantee for potentially bad clients.
  • Potentially bad clients: The analysis separately aims to show that clients in B make only a small contribution to total solution cost.This requires bounding their aggregate contribution beyond the individual connection-cost inequalities.

8.4 Showing that α-values are stable

The analysis proves that α-values remain stable during RaisePrice, enabling a close sequence of dual solutions and controlling the potentially bad clients.

  • Close solution sequence: Stable α-values imply that RaisePrice produces a close sequence of consecutive solutions.The section introduces parameters K, σ, and εz so the successive solutions remain close enough for the later combination argument.
  • Stability bounds: Lemma 8.8 bounds the α-values of clients sharing a tight facility by a factor of 192.If one client has a tight edge to a facility, every other client with a tight edge there has α_{j′} ≤ 192α_j.
  • Stability proof: Clients sharing a tight facility are constrained by the same stability inequality throughout Algorithm 1.The proof preserves the inequality under both α-value increases and Sweep-induced decreases.
  • Stability bounds: Each Sweep call changes every α_j by at most n^-2.The bound follows from controlling increases and decreases across bucket levels.

8.5 Handling dense clients

The analysis isolates dense facilities and clients as troublesome cases, then bounds their costs using special facilities, token arguments, and a randomized shift parameter. These bounds support construction of a roundable solution.

  • Motivation: A small fraction γ^4 of clients can appear in B during RaisePrice, but this alone is insufficient to charge their extra service cost to OPT_k.The analysis therefore separately handles dense clients and facilities.
  • Definitions: Dense facilities are defined through γ-close neighborhoods, and dense clients are those lying in such neighborhoods.These sets depend only on the input solution and the integral solution passed to RaisePrice.
  • Non-dense clients: The total α(0)-value of non-dense clients can be charged to OPT_k using a partition by distance and a fractional token argument.Clients farther than the γ threshold distribute tokens to facilities in IS(0), whose total received tokens are bounded.
  • Shift selection: Selecting the shift parameter σ uniformly from [0, K/2) bounds the expected bad-client contribution, and choosing the minimizing shift gives the corresponding deterministic bound.The minimum over σ is at most the expectation over a uniformly random shift; the selection can be derandomized because the number of options is constant.
  • Dense clients: Dense clients in DD ∩ B are bounded using facilities of F_S, yielding either a tight facility or a special facility for each such client.This improves the bound for the troublesome dense clients and enables a roundable solution.

8.6 Showing that each solution is roundable and completing the analysis

The paper proves that every solution produced by Algorithm 1 is roundable and that RaisePrice produces sufficiently many close solutions in polynomial time. The analysis completes the structural and runtime guarantees needed for the algorithm.

  • Roundability: Every solution (α, z) produced by Algorithm 1 is roundable.This follows from the established properties of the constructed dense and bad-client sets.
  • Feasibility: Each produced solution is feasible for DUAL(λ + ϵz), with ϵz < 1, and facility penalties satisfy λ ≤ z_i ≤ λ + 1/n.The construction maintains these feasibility and penalty bounds throughout the analysis.
  • Roundability: The constructed solution satisfies the required properties for clients outside B, clients in B ∩ DD, and the remaining clients in B \ DD.These cases use tight or special facilities and define the remaining bad clients as DB = B \ DD.
  • Runtime and output: RaisePrice runs in polynomial time and produces a polynomial number of close roundable solutions.The close property follows from Proposition 8.10, while roundability follows from Proposition 8.18.
  • Runtime and output: RaisePrice makes at most n^O(ϵ^-1γ^-4) Sweep calls and executes γ^4O(log n) stages before all clients are decided.The bounds use the upper limit M on α-values and the stage thresholds θ_s.

A Implementation of QuasiSweep

The polynomial QuasiSweep implementation advances client prices between discrete events, updating active clients, buckets, tight facilities, tight edges, and decreasing clients. Each event type occurs only polynomially often.

  • Procedure: QuasiSweep changes each client’s α-value at speed 0, 1, or −|A| while θ increases at speed 1.The next event is computed, values are updated to that time, and the active set and speeds are revised.
  • Events: Five events govern the implementation: clients join A, θ changes buckets, facilities become tight, clients gain tight edges, or clients enter θ’s bucket.These events capture the discrete changes in the process.
  • Event bounds: Bucket changes occur O(ϵ^-1 log(n)) times, while facility-tightness and tight-edge events occur at most m and nm times, respectively.Client-joining events occur exactly n times, and the final bucket event occurs at most n times.
  • Complexity: The number of events is polynomial, and the next event can be computed in polynomial time.Therefore, QuasiSweep admits a polynomial-time implementation.

B Implementation of Sweep

Sweep is implemented by repeatedly advancing to the next event while maintaining active and decreasing clients. The event structure yields polynomially many events and polynomial running time.

  • Procedure: Sweep increases θ at rate 1 and changes α_j at rates 1 for active clients, −|A| for decreasing clients, and 0 otherwise.The implementation updates all values and then recomputes A and the decreasing set after each event.
  • Events: Sweep’s basic events include bucket changes, α_j reaching constants, facilities becoming tight witnesses, and clients entering or leaving active or decreasing sets.Each event is tied to a specific condition involving θ, α-values, tight edges, or potentially tight facilities.
  • Event bounds: Events that change A occur only polynomially often, and each client can be removed from D at most a polynomial number of times.This follows by associating each change with one of the enumerated event types and fixed constants or facilities.
  • Complexity: The next event can be calculated in polynomial time, and Sweep therefore runs in time polynomial in the numbers of clients and facilities.The implementation maintains exact event times while preserving the sweep dynamics.

C Bounding the Distances

The section reduces k-means instances to equivalent bounded-distance instances, losing only a factor 1+100/n^2 in approximation quality. It establishes the reduction for general metrics and Euclidean metrics while preserving polynomial-time computability.

  • Reduction guarantee: Lemma C.1 bounds every client–facility squared distance in [1, n^6] while increasing the approximation ratio by at most 1+100/n^2.The transformed instance preserves the number of facilities, clients, and the value of k.
  • Metric distance: The metric construction rescales distances, caps excessively large values, and raises distances below one, preserving metricity and transferring ρ-approximate solutions with factor ρ(1+100/n^2).The proof uses intermediate instances I1, I2, and I′ and bounds OPT(I1) between n^3/100 and n^3.
  • Euclidean metric: Translating cluster centroids to the origin and adding one coordinate per cluster separates clusters while keeping the maximum squared distance at most n^6.The construction preserves within-cluster distances and ensures high-quality solutions connect clients only to facilities in the same cluster.
  • Reduction guarantee: The complete distance-bounding procedure runs in polynomial time.This establishes efficient preprocessing for the bounded-distance instance used by the later algorithm.
Loading 1612.07925v2…