17 czerwca 2024 11:00
[Seminarium ZOK] Fateme Abbasi: Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
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 and in algorithmic
fairness. Given a constant z>1, the input to Robust (k, z)-Clustering
is a set P of n points in a metric space, a weight function and a
positive integer k. Further, each point belongs to one (or more) of
the 'm' many different groups. Our goal is to find a set X of k
centers such that the cost function is minimized.
We prove the following results:
1) For a universal constant epsilon, we devise a
3^z(1-epsilon)-factor FPT approximation algorithm for Robust (k,
z)-Clustering in discrete high-dimensional Euclidean spaces where the
set of potential centers is finite.
2) We show that Robust (k, z)-Clustering in discrete Euclidean spaces
is hard to approximate for FPT algorithms, even if we consider the
special case k-Center in logarithmic dimensions.
3) We obtain an EPAS for Robust (k, z)-Clustering in discrete
Euclidean spaces when the dimension is sublogarithmic.
Joint work with: Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook,
Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, Roohani Sharma,
Joachim Spoerhase