Lossy Kernelization of Same-Size Clustering

2021/07/15 by Sayan Bandyapadhyay, Bandyapadhyay, Sayan, Fedor V. Fomin +7
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.2107.07383

arxiv created 2021/07/15 · arxiv updated 2021/07/16

Abstract

In this work, we study the k-median clustering problem with an additional equal-size constraint on the clusters, from the perspective of parameterized preprocessing. Our main result is the first lossy (2-approximate) polynomial kernel for this problem, parameterized by the cost of clustering. We complement this result by establishing lower bounds for the problem that eliminate the existences of an (exact) kernel of polynomial size and a PTAS.

Related

• Coresets for k-Means and k-Median Clustering and their Applications
• Coresets for constrained k-median and k-means clustering in low dimensional Euclidean space
• Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering
• A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering
• On Tight Robust Coresets for k-Medians Clustering