Projects per year
Abstract
This paper considers the wellstudied algorithmic regime of designing a $(1+\epsilon)$approximation algorithm for a kclustering problem that runs in time $f(k,\epsilon)poly(n)$ (sometimes called an efficient parameterized approximation scheme or EPAS for short1). Notable results of this kind include EPASes in the highdimensional Euclidean setting for kcenter [Badŏiu, HarPeled, Indyk; STOC’02] as well as kmedian, and kmeans [Kumar, Sabharwal, Sen; J. ACM 2010]. Our main contribution is a clean and simple EPAS that settles more than ten clustering problems (across multiple wellstudied objectives as well as metric spaces) and unifies wellknown EPASes. More specifically, our algorithm gives EPASes in the following settings:•Clustering objectives: kmeans, kcenter, kmedian, priority kcenter, $\ell$centrum, ordered kmedian, socially fair kmedian (aka robust kmedian), or any other objective that can be formulated as minimizing a monotone (not necessarily symmetric!) norm of the distances of the points from the solution (generalizing the symmetric formulation introduced by Chakrabarty and Swamy [STOC’19]).•Metric spaces: Continuous highdimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics. Prior to our results, EPASes were only known for vanilla clustering objectives (kmeans, kmedian, and kcenter) and each such algorithm is tailored to work for the specific input metric and clustering objective (e.g., EPASes for k means and kcenter in $\mathbb{R}^{d}$ are conceptually very different). In contrast, our algorithmic framework is applicable to a wide range of wellstudied objective functions in a uniform way, and is (almost) entirely oblivious to any specific metric structures and yet is able to effectively exploit those unknown structures. In particular, our algorithm is not based on the (metric and objectivespecific) technique of coresets. Key to our analysis is a new concept that we call bounded $\epsilon$scatter dimension—an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension(often used as a source of algorithmic tractability for geometric problems). Our main technical result shows that two conditions are essentially sufficient for our algorithm to yield an EPAS on the input metric M for any clustering objective:(i)The objective is described by a monotone norm, and(ii)the $\epsilon$scatter dimension of M is upper bounded by a function of $\epsilon$.1Quick remarks: (i) An EPAS is not comparable to polynomial time approximation schemes (PTAS), (ii) before the term EPAS was invented some researchers call this type of approximation schemes a PTAS or simply an approximation scheme (in clustering, it is often assumed that k is small) [1], [2], and (iii) both EPAS and PTAS are implied by the existence of efficient polynomial time approximation schemes (EPTAS).
Original language  English 

Title of host publication  2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) 
Publisher  IEEE 
Pages  13771399 
Number of pages  23 
ISBN (Electronic)  9798350318944 
ISBN (Print)  9798350318951 
DOIs  
Publication status  Published  2023 
MoE publication type  A4 Conference publication 
Event  Annual Symposium on Foundations of Computer Science  Santa Cruz, United States Duration: 6 Nov 2023 → 9 Nov 2023 Conference number: 64 
Conference
Conference  Annual Symposium on Foundations of Computer Science 

Abbreviated title  FOCS 
Country/Territory  United States 
City  Santa Cruz 
Period  06/11/2023 → 09/11/2023 
Keywords
 Measurement
 Computer science
 Atmospheric measurements
 Clustering algorithms
 Extraterrestrial measurements
 Approximation algorithms
 Particle measurements
Fingerprint
Dive into the research topics of 'Parameterized Approximation Schemes for Clustering with General Norm Objectives'. Together they form a unique fingerprint.Projects
 2 Finished

Combinatorics of Graph Packing and Online Binary Search Trees.
Chalermsook, P., Khodamoradi, K. & Obscura Acosta, N.
01/09/2020 → 31/08/2022
Project: Academy of Finland: Other research funding

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P., Jindal, G., Franck, M., Khodamoradi, K., Yingchareonthawornchai, S., Gadekar, A., Orgo, L., Spoerhase, J. & Jiamjitrak, W.
01/02/2018 → 31/01/2024
Project: EU: ERC grants