## Abstract

We consider the well-studied Robust (k, z)-Clustering problem, which generalizes the classic k-Median, k-Means, and k-Center problems and arises in the domains of robust optimization [Anthony, Goyal, Gupta, Nagarajan, Math. Oper. Res. 2010] and in algorithmic fairness [Abbasi, Bhaskara, Venkatasubramanian, 2021 & Ghadiri, Samadi, Vempala, 2022]. Given a constant z ≥ 1, the input to Robust (k, z)-Clustering is a set P of n points in a metric space (M, δ), a weight function w : P → R_{≥0} and a positive integer k. Further, each point belongs to one (or more) of the m many different groups S1, S2, . . ., Sm ⊆ P. Our goal is to find a set X of k centers such that max_{i}∈[m_{]}^{P}_{p∈Si} w(p)δ(p, X)^{z} is minimized. Complementing recent work on this problem, we give a comprehensive understanding of the parameterized approximability of the problem in geometric spaces where the parameter is the number k of centers. We prove the following results: (i) For a universal constant η0 > 0.0006, we devise a 3^{z}(1−η0)-factor FPT approximation algorithm for Robust (k, z)-Clustering in discrete high-dimensional Euclidean spaces where the set of potential centers is finite. This shows that the lower bound of 3^{z} for general metrics [Goyal, Jaiswal, Inf. Proc. Letters, 2023] no longer holds when the metric has geometric structure. (ii) We show that Robust (k, z)-Clustering in discrete Euclidean spaces is (p3/2−o(1))-hard to approximate for FPT algorithms, even if we consider the special case k-Center in logarithmic dimensions. This rules out a (1 + ϵ)-approximation algorithm running in time f(k, ϵ)poly(m, n) (also called efficient parameterized approximation scheme or EPAS), giving a striking contrast with the recent EPAS for the continuous setting where centers can be placed anywhere in the space [Abbasi et al., FOCS’23]. (iii) However, we obtain an EPAS for Robust (k, z)-Clustering in discrete Euclidean spaces when the dimension is sublogarithmic (for the discrete problem, earlier work [Abbasi et al., FOCS’23] provides an EPAS only in dimension o(log log n)). Our EPAS works also for metrics of sub-logarithmic doubling dimension.

Original language | English |
---|---|

Title of host publication | 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024 |

Editors | Karl Bringmann, Martin Grohe, Gabriele Puppis, Ola Svensson |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

ISBN (Electronic) | 9783959773225 |

DOIs | |

Publication status | Published - Jul 2024 |

MoE publication type | A4 Conference publication |

Event | International Colloquium on Automata, Languages, and Programming - Tallinn, Estonia Duration: 8 Jul 2024 → 12 Jul 2024 Conference number: 51 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 297 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | International Colloquium on Automata, Languages, and Programming |
---|---|

Abbreviated title | ICALP |

Country/Territory | Estonia |

City | Tallinn |

Period | 08/07/2024 → 12/07/2024 |

## Keywords

- approximation algorithms
- Clustering
- parameterized complexity