CISPA
Browse

Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces

Download (1.02 MB)
conference contribution
posted on 2024-07-25, 12:39 authored by Fateme Abbasi, Sandip Banerjee, Jaros law Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel MarxDániel Marx, Roohani Sharma, Joachim Spoerhase
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 → ℝ_{≥ 0} and a positive integer k. Further, each point belongs to one (or more) of the m many different groups S_1,S_2,…,S_m ⊆ P. Our goal is to find a set X of k centers such that max_{i ∈ [m]} ∑_{p ∈ S_i} 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)] 1) For a universal constant η₀ > 0.0006, we devise a 3^z(1-η₀)-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. 2) We show that Robust (k,z)-Clustering in discrete Euclidean spaces is (√{3/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]. 3) 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.

History

Editor

Bringmann K ; Grohe M ; Puppis G ; Svensson O

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Colloquium on Automata Languages and Programming (ICALP)

Journal

51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Volume

297

Page Range

6:1-6:19

Publisher

Schloss Dagstuhl – Leibniz-Zentrum für Informatik

BibTeX

@inproceedings{Abbasi:Banerjee:Byrka:Chalermsook:Gadekar:Khodamoradi:Marx:Sharma:Spoerhase:2024, title = "Parameterized Approximation For Robust Clustering in Discrete Geometric Spaces", author = "Abbasi, Fateme" AND "Banerjee, Sandip" AND "Byrka, Jaros law" AND "Chalermsook, Parinya" AND "Gadekar, Ameet" AND "Khodamoradi, Kamyar" AND "Marx, Dániel" AND "Sharma, Roohani" AND "Spoerhase, Joachim", editor = "Bringmann, Karl" AND "Grohe, Martin" AND "Puppis, Gabriele" AND "Svensson, Ola", year = 2024, month = 7, journal = "51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)", pages = "6:1--6:19", publisher = "Schloss Dagstuhl – Leibniz-Zentrum für Informatik", issn = "1868-8969", doi = "10.4230/LIPIcs.ICALP.2024.6" }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC