CS Paper Radar

An experimental evaluation of static k-center clustering algorithms on graphs

Sebastian Forster, Martin Grösbacher

cs.DS ·submitted 2026-10-21 14:08 UTC · v1
published

Abstract

The $k$-center problem is one of the most fundamental clustering problems and has applications in a wide range of areas, including facility location, network design, data mining, and machine learning. Given a set of objects together with a distance measure, the goal is to select $k$ centers such that the maximum distance from any object to its closest center is minimized. The $k$-center problem has been studied extensively from a theoretical perspective, both in metric spaces and on graphs. While there have been experimental studies for $k$-center clustering in metric spaces, a comprehensive experimental comparison of graph-based $k$-center algorithms on large-scale graphs is still lacking. In this paper, we bridge this gap by evaluating a set of algorithms ranging from classical approaches such as Gonzalez's greedy algorithm [TCS 1985], an algorithm based on the framework established by Hochbaum and Shmoys [Math. Oper. Res. 1985], to more recent methods, including algorithms by Thorup [SICOMP 2001] and Abboud et al. [SOSA 2023]. Our study considers both running time, solution quality and the effects of parallelism on a variety of synthetic and real-world datasets. Our goal is to provide a comprehensive comparison of state-of-the-art $k$-center algorithms on graphs and identify the strengths and weaknesses of different approaches in practice.

Comment
to appear in ALENEX 2027

Closest papers

Nearest neighbours by meaning across the whole index.

A Configuration-LP Framework for Connected $k$-Median Clustering

cs.DS ·2026-08-28 ·Kushagra Chatterjee, Rojin Rezvan, Ali Vakilian
hot direction similarity 0.68
Abstract · This paper has been accepted in Approx 2026

We study the \emph{connected $k$-median} clustering problem, a clustering problem that augments the classical $k$-median objective with connectivity constraints. We focus on the \emph{overlapping} variant of the problem, where clusters are allowed to share vertices. In addition to a metric space $(V,d)$, the input contains a connected graph $G$ on the same vertex set $V$ of size $n$. The goal is to select at most $k$ centers $C$ and assign vertices to them so as to minimize the $k$-median cost (i.e., $\sum_{v\in V} d(v,C)$), subject to the constraint that each cluster induces a connected subgraph of $G$. Since the metric space and the connectivity graph are independent, the problem is significantly more challenging than standard clustering. Eube et al.~\cite{eube2025esa} showed that even the assignment version is $Ω(\log n)$-hard to approximate and gave approximation algorithms with guarantees depending polynomially on $k$. We develop a configuration-LP-based framework that combines covering LP techniques with a rooted minimum-density oracle. For the assignment version, we obtain an $O(\log^2 n)$-approximation. For the general version, we develop a bicriteria framework that opens $O(k\log n)$ centers while achieving an $O(\log^2 n)$-approximation in cost. %Our results provide a different LP-based approach for handling connectivity constraints in clustering problems and demonstrate that configuration LPs, covering LPs, and rooted density oracles can be combined effectively to obtain approximation guarantees for clustering objectives under graph-theoretic constraints.

0.30

Competitive Online Clustering with Movement Cost

cs.DS ·2026-10-16 ·Christian Coester, Yichen Huang, Michael Mitzenmacher
top venue similarity 0.67
Abstract · To appear in SODA 2027

We study the problem of online clustering with movement cost, which generalizes the fundamental $k$-server problem. At each time step, the algorithm is given a set of points in a metric space and must choose $k$ cluster centers. The cost incurred is the sum of the clustering cost at each time step and the total distance that the centers move over time. Prior work established competitive algorithms for the case $k\in\{1,2\}$ on the line metric with the $k$-median clustering objective; under the $k$-median objective, this problem is also known as facility reallocation. We substantially generalize these results to arbitrary $k$, general metric spaces, and a broad class of clustering objectives. Specifically, we consider clustering costs defined as a norm of the distance vector from points to their nearest center, which subsumes the $k$-median, $k$-center, and (square root of) $k$-means objectives, and provide an asymptotically optimal $O(k)$-competitive randomized algorithm against adaptive online adversaries. The algorithm is based on a reduction to the $k$-server problem, establishing a tight connection between the problems. In this reduction, $k$-server requests are generated by Poisson processes, whose arrival rates evolve in continuous time and are driven by a dual representation of the clustering costs. Our method of using Poissonization in this context may also be of independent interest. We demonstrate another use of the idea by deriving similar reductions for batched set chasing problems. We also consider a different family of clustering objectives defined as a norm of the vector of cluster radii, which subsumes the sum-$k$-radii and the $k$-center objectives, and give a tight $O(k)$-competitive deterministic algorithm on the line.

0.62

Parameterized and Streaming Algorithms for Euclidean Fair $k$-Center Clustering

cs.LG cs.AI ·2026-09-06 ·Zeyu Lin, Chaoqi Jia, Longkun Guo, Chao Chen
top venue similarity 0.64
Abstract

Motivated by the growing importance of fairness in machine learning, fair $k$-center clustering has attracted considerable research attention as a fundamental problem. In this problem, a dataset is partitioned into $m$ disjoint groups, and the objective is to select $k$ data points as centers, subject to upper bounds on the number of centers chosen from each group, aiming to minimize the maximum distance between any data point and its assigned center. Focusing on Euclidean spaces, which are ubiquitous in machine learning applications, we first develop a parameterized approximation algorithm for Euclidean fair $k$-center with an approximation ratio of $2.732$. By incorporating this algorithm as a post-processing stage into a one-pass streaming framework for large-scale data, we obtain an approximation ratio of $4.464$. These ratios can be further respectively improved to $2.414$ and $3.828$ with a runtime exponential on $k$. To ensure polynomial-time complexity, we further design a one-pass streaming algorithm with an approximation ratio of $4.732$, which can be further improved to $4.42$, outperforming the state-of-the-art ratio. Finally, extensive experiments show that our methods significantly outperform state-of-the-art approaches in terms of clustering accuracy.

0.40

Constant-Factor Approximation for Capacitated Clustering in Low Dimension with $(1+ε)k$ Centers

cs.CG cs.DS ·2026-10-29 ·Kangke Cheng, Guanlin Mo, Hu Ding
similarity 0.62
Abstract

In many applications of $k$-median and $k$-means, including load balancing and redistricting, each center can serve only a bounded number of clients. This leads to capacitated clustering, in which a client may be forced to use a distant center because all nearby ones are full. This loss of locality defeats the techniques behind approximation schemes, and no constant-factor approximation is known in general metrics even for capacitated $k$-median. A long line of work therefore opens $K=k+\lfloorεk\rfloor$ centers for a fixed $ε\in(0,1]$, while respecting the capacities exactly. We give a deterministic polynomial-time algorithm for uniform soft capacities in low dimension, that is, when the clients or the center locations have bounded doubling dimension. With $K$ centers, its ratio is $3-2ε$ for $k$-median and $9-8ε$ for $k$-means, or $5-4ε$ in $\mathbb{R}^d$. Apart from $k$-median in the plane, these are the first polynomial-time ratios bounded by a constant independent of $ε$; previously, the best ratio was $O(ε^{-2}\log(1/ε))$, even for $k$-median. We also obtain ratios that stay bounded as $ε\to0$ for non-uniform and hard capacities in low dimension, and ratios polylogarithmic in $1/ε$ in general metrics. Our approach starts from a simple structural observation: a near-optimal uncapacitated solution can be split into fewer than $2k$ capacity-respecting blocks, so $2k$ centers already suffice, one per block. Our main tool, the rescue lemma, shows that once every block that sends clients to a center of the optimal solution is rescued (given a private center), that center can be closed, so each extra center effectively rescues about two blocks. This lets $\lfloorεk\rfloor$ extra centers rescue nearly an $ε$-fraction of the blocks, yielding the linear dependence on $ε$ in our ratios.

0.16

When Shall We $k$ Meet Again? Tight Algorithms for Diameter and Radius under the Meet Distance

cs.DS ·2026-09-18 ·Yael Kirkpatrick, John Kuszmaul, Merey Temirzinova, Virginia Vassilevska Williams
theory similarity 0.62
Abstract · 20 pages

Finding an optimal meeting point for a collection of agents on a directed graph is a classical problem studied in the context of network analysis, operations research and computational geometry. In this work, we use the two objectives of optimal meeting points examined in the literature to study two notions of meet-distance: $d^{\max}(u,v)$, the minimum over all meeting points $w$ of $\max(d(u,w), d(v,w))$; and $d^+(u,v)$, the minimum over all meeting points of $d(u,w) + d(v,w)$. These values measure the minimum time and minimum total distance required for two agents to meet. We initiate the fine-grained study of fundamental graph parameters under the two notions of meet-distance, namely the diameter, radius and eccentricities. For general directed graphs, we give an $\tilde{O}(m\sqrt{n})$ time algorithm for computing a 2-approximation to both notions of meet-diameter and show that this result is optimal under SETH. In contrast, we show that such a result is unattainable for the meet-radius as any finite approximation requires quadratic time under the Hitting Set Conjecture. For directed acyclic graphs, we obtain stronger results. We compute the meet$^{\max}$-diameter exactly in linear time and give a linear-time $2$-approximation for the meet$^{+}$-diameter. We complement the latter with a quadratic-time lower bound for any $(3/2-\varepsilon)$-approximation under SETH, yielding a separation between the two meet-distance objectives. Finally, we study the generalized meet-distance of $k$-tuples of vertices. For every positive integer $\ell$, we reduce the problem of $\ell$-approximating the $k$-point meet-diameter to computing an exact meet-diameter on smaller tuples, obtaining an $\ell$-approximation in time \[ O\!\left( mn+ \ell \left\lceil k^{1/\ell}\right\rceil n^{\left\lceil k^{1/\ell}\right\rceil+1} \right). \]

0.28

OverclusterDRG: a Deterministic, LP-Free Heuristic for Robust $k$-Center

cs.LG ·2026-11-13 ·Rudra Bhardwaj, Rajni Dabas, Neelima Gupta
similarity 0.62
Abstract · 11 pages, 7 figures, 8 tables

The $k$-center problem is a fundamental formulation for metric clustering. However, its min-max objective is highly sensitive to outliers, motivating the Robust $k$-Center (R$k$C) formulation which permits excluding up to $z$ points as outliers. Existing algorithms for R$k$C suffer from scalability issues: LP rounding relies on fractional relaxations that scale poorly, known combinatorial approximation algorithms are computationally expensive due to radius guessing, and scalable randomized heuristics require exponential trial multipliers to guarantee success. We present OverclusterDRG, a deterministic, LP-free heuristic for R$k$C. The algorithm leverages the theoretical insight of farthest-point oversampling -- adding exactly $z$ extra candidates to the center set to absorb outliers -- followed by a forward-greedy initialization and a $1$-swap local search. Evaluations across real-world datasets show that OverclusterDRG attains a mean approximation ratio of 1.147 against fractional LP lower bounds on the UCI Adult dataset, outperforming state-of-the-art baselines in both clustering quality and speed. By avoiding subset-guessing and exponential trial multipliers, it scales smoothly to $n=10^5$ points where LP solvers and theoretical algorithms become intractable.

0.20

Dimension Reduction and Coresets for Min-Sum $k$-Clustering

cs.DS cs.CG ·2026-10-28 ·Asaf Dallal, Robert Krauthgamer
similarity 0.62
Abstract

The min-sum $k$-clustering problem asks to partition an input of $n$ points into $k$ clusters so as to minimize the total pairwise distance within clusters. It is a natural alternative to center-based objectives when the data is not well captured by a small set of representative points. We study for this problem two standard sketching methods, dimension reduction and coresets, which represent the input more compactly while preserving the min-sum cost of every $k$-partition up to $1\pm\varepsilon$ factor. Our first contribution addresses dimension reduction in Euclidean space. The Johnson-Lindenstrauss (JL) Lemma readily implies that a random linear map to target dimension $t=O(\varepsilon^{-2}\log n)$ preserves, with high probability, the min-sum cost of all $k$-partitions. We show that target dimension $t=O(\varepsilon^{-2}(ddim\cdot\log(1/\varepsilon)+\log k+\log\log n))$ suffices for Euclidean inputs of doubling dimension at most $ddim$, and moreover this bound is nearly optimal. We also show that target dimension $t=O(\varepsilon^{-2}(\log(1/\varepsilon)+\log k+\logΔ))$ suffices for Euclidean inputs of aspect ratio at most $Δ$. Our second contribution is to design the first $\varepsilon$-coreset for metric min-sum $k$-clustering. It is actually a movement-based coreset, has size $(1/\varepsilon)^{O(ddim)} k\log n$ for inputs of doubling dimension at most $ddim$, and can be constructed in randomized near-linear-time. We further use these coresets to design streaming algorithms for the problem.

0.18

Coresets for Capacitated Clustering via Dual Concentration

cs.DS cs.CGcs.LG ·2026-11-06 ·Milind Prabhu, Chris Schwiegelshohn, Sudarshan Shyam, Erik Waingarten
similarity 0.61
Abstract

We study coresets for clustering problems, focusing on the classical $k$-median and $k$-means objectives. A coreset is a small weighted summary of the input data that approximately preserves the clustering cost for every choice of centers. Such summaries are a central tool for scaling clustering algorithms to large datasets. In this work, we consider the capacitated setting, where the clustering is subject not only to choosing centers but also to respecting prescribed cluster-size constraints. This model is a natural generalization of standard clustering and has been widely studied, but its coreset complexity is less well understood. For finite metric spaces, we obtain optimal-size coresets; surprisingly, these match the best-known bounds for unconstrained clustering. We also give improved coreset bounds in Euclidean space, notably the first coresets with near-linear dependence in $k$ while being independent of the dimension and input size. The main new technical ingredients are concentration bounds for the dual solutions of min-cost flow problems, which allow for both significantly simpler and tighter analyses of the underlying sampling distribution used in the coreset construction.

0.12