A Simple PTAS for Weighted k k -means and Sensor Coverage

Akash Pareek, Supratim Shit · 2025

Read A Simple PTAS for Weighted k k -means and Sensor Coverage by Akash Pareek, Supratim Shit (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-06460.txt.

Introduction

Akash Pareek and Supratim Shit give a simple near optimal algorithm for weighted clustering, in a 2025 paper. Clustering groups points around a set of centers, and in many tasks each point carries a weight for its importance or frequency. Most past near optimal methods for this weighted case lean on coresets, or small stand in data sets.

Their method skips coresets and builds on a known frame for the unweighted case, with weighted sampling in place of plain sampling. It returns centers whose cost sits within a small factor of the best. As a use case, they get the same type of guarantee for placing sensors to cover an area.

Catalog record

CREATORAkash Pareek, Supratim Shit
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-06460

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Simple PTAS for Weighted k k -means and Sensor Coverage Akash Pareek, Supratim Shit Abstract Clustering is a fundamental technique in data analysis, with the k k -means problem being one of the most widely studied objectives due to its simplicity and broad applicability. In many practical scenarios, data points come with associated weights that reflect their importance, frequency, or confidence. Given a weighted point set P ⊂ ℝ d P\subset\mathbb{R}^{d} , where each point p ∈ P p\in P has a positive weight w p w_{p} , the goal is to compute a set of k k centers 𝒞 = { c 1 , c 2 , … , c k } ⊂ ℝ d \mathcal{C}=\{c_{1},c_{2},\dots,c_{k}\}\subset\mathbb{R}^{d} that minimizes the weighted clustering cost: Δ w ​ ( P , 𝒞 ) = ∑ p ∈ P w p ⋅ d ​ ( p , 𝒞 ) 2 , \Delta^{w}(P,\mathcal{C})=\sum_{p\in P}w_{p}\cdot d(p,\mathcal{C})^{2}, where d ⁡ ( p , 𝒞 ) d(p,\mathcal{C}) denotes the Euclidean distance from p p to its nearest center in 𝒞 \mathcal{C} . Although most existing coreset -based algorithms for k k -means extend naturally to the weighted setting and provide a PTAS, no prior work has offered a simple, coreset-free PTAS designed specifically for the weighted k k -means problem. In this paper, we present a simple PTAS for weighted k k -means that do not rely on coresets. Building upon the framework of Jaiswal, Kumar, and Sen [ JKS12 ] for the unweighted case, we extend the result to the weighted setting by using the weighted 𝒟 2 {\mathcal{D}^{2}} -sampling technique. Our algorithm runs in time n ​ d ⋅ 2 O ~ ​ ( k 2 / ϵ ) nd\cdot 2^{\tilde{O}(k^{2}/\epsilon)} and outputs a set of k k centers whose total clustering cost is within a ( 1 + ϵ ) (1+\epsilon) -factor of the optimal cost. As a key application of the weighted k k -means, we obtain a PTAS for the sensor coverage problem , which can also be viewed as a continuous locational optimization problem. For this problem, the best-known result prior to our work was an O ⁡ ( log ⁡ k ) O(\log k) -approximation due to Deshpande [ Des14 ] . In contrast, our algorithm guarantees a ( 1 + ϵ ) (1+\epsilon) -approximation to the optimal coverage cost even before applying refinement steps like Lloyd’s descent. 1 Introduction Clustering is one of the fundamental steps in the analysis of large datasets. A classical and widely used approach to cluster data is the k -means clustering , where the input is a point set P\subset\mathbb{R}^{d} of size n , and the objective is to compute a set of k centers \mathcal{C}=\{c_{1},c_{2},\dots,c_{k}\}\subset\mathbb{R}^{d} that minimizes the total squared distance of each point to its nearest center, formally given by: \Delta(P,\mathcal{C})=\sum_{p\in P}d(p,\mathcal{C})^{2}, where d(p,\mathcal{C})^{2}=\min_{c\in\mathcal{C}}\|p-c\|^{2} denotes the squared Euclidean distance from point p to the closest center in \mathcal{C} . As the objective function of k -means clustering is both intuitive and computationally well-structured, it has been widely applied across various domains, including machine learning, image processing, dimensionality reduction, and community detection in large-scale graphs. The k -means objective implicitly assumes that all the points in the dataset are equally important. However, in many practical applications, data points may have different importance or influence. This asymmetry can be naturally modeled by associating each point p\in P with a non-negative real-value weight w_{p} , representing its significance in the dataset. This leads to the weighted k -means problem, which generalizes the k -means by minimizing the weighted clustering cost: \Delta^{w}(P,\mathcal{C})=\sum_{p\in P}w_{p}\cdot d(p,\mathcal{C})^{2}. Here, the goal is to compute k centers \mathcal{C}\subset\mathbb{R}^{d} that minimize \Delta^{w}(P,\mathcal{C}) . This formulation captures scenarios in which each data point contributes to the clustering objective proportionally to its associated weight. Weighted k -means arises naturally in a variety of real-world applications, including those involving aggregated observations, non-uniform sampling frequencies, varying confidence levels, geospatial analysis, document and text clustering, imbalanced datasets, and so on. Despite extensive research on the k -means problem, it remains NP-hard to compute an optimal set of centers \mathcal{C} even for the case k=2 [ Das08 ] . A widely used heuristic for solving k -means in practice is Lloyd’s algorithm [ Llo82 ] . While Lloyd’s algorithm often performs well empirically, it is known to converge to local minima and may exhibit poor worst-case behavior [ AV06b ] . To address the sensitivity of Lloyd’s Algorithm, Arthur and Vassilvitskii proposed the k -means++ algorithm [ AV06a ] , that instead of choosing the initial k -centers at random (like Lloyd’s), picks the initial k centers using {\mathcal{D}^{2}} -sampling. The {\mathcal{D}^{2}} -sampling can be informally defined as follows: Let {\mathcal{C}}^{\prime} be the set of centers chosen by the {\mathcal{D}^{2}} -sampling. Initially, {\mathcal{C}}^{\prime} is empty. The first center is chosen at random and inserted into the set {\mathcal{C}}^{\prime} . Any other point p\in P is selected as the next center with probability d(p,{\mathcal{C}}^{\prime}) . This process is continued till {\mathcal{C}}^{\prime} has exactly k centers. Now, the set {\mathcal{C}}^{\prime} is used as initial centers for Lloyd’s algorithm. Using this {\mathcal{D}^{2}} -sampling technique, Arthur and Vassilvitskii showed that the k -means++ algorithm exhibits O(\log k) -approximation to the optimal clustering. The k -means problem being NP-hard, researchers always try to find good approximate solutions for the problem, i.e., to return a set of centers such that the k -means cost is close to the optimal k -means cost. Matousek [ Mat00 ] gave a (1+\epsilon) -approximation which runs in time O(n\log k\hskip 2.84544ptn\epsilon^{-2k^{2}d}) . Kanungo et al. [ KMN+02 ] gave a (9+\epsilon) -approximation algorithm which runs in time O(n\log n+n\epsilon^{-d}\log(1/\epsilon)+n^{2}k^{3}\log n) . Kumar et al. [ KSS04 ] also gave an (1+\epsilon) -approximation which runs in time nd\cdot 2^{(k/\epsilon)^{O(1)}} . Jaiswal et al. [ JKS12 ] gave a simple {\mathcal{D}^{2}} -sampling based (1+\epsilon) -approximation which runs in time nd\cdot 2^{k}\cdot 2^{\tilde{O}(k/\epsilon)} . There are many other works related to k -means, we mention a few of them in Section 1.2 . In addition to the above results for k -means, a lot of work for k -means has focused on designing coreset-based algorithms . A coreset is a small, weighted subset of the input data that approximates the original data. For the k -means objective function, the clustering cost on the coreset closely matches the cost on the full dataset. Coreset-based approaches typically proceed in two steps. First, a coreset is constructed, which is the most technically involved part of the process. Unlike simple sampling techniques, coreset construction often requires careful sensitivity analysis, importance sampling, and geometric partitioning, making it algorithmically and analytically more complicated. The second step applies a possibly exhaustive search or approximation algorithm on the small coreset instead of the full dataset. Since the size of the coreset is usually independent of the size of the original input (and often depends only on parameters like k , d , and \epsilon ), this enables efficient PTAS for k -means. All coreset-based algorithms for unweighted k -means naturally extend to the weighted setting, thereby yielding PTAS for weighted k -means as well. One of the earliest such constructions is due to Har-Peled and Mazumdar [ HM04

Read the complete text