Tight FPT Approximation for Socially Fair Clustering

Abstract

In this work, we study the socially fair k-median/k-means problem. We are given a set of points P in a metric space X with a distance function d(.,.). There are groups: P_1,,P_ P. We are also given a set F of feasible centers in X. The goal in the socially fair k-median problem is to find a set C F of k centers that minimizes the maximum average cost over all the groups. That is, find C that minimizes the objective function (C,P) _j \ _x P_j d(C,x)/|P_j| \, where d(C,x) is the distance of x to the closest center in C. The socially fair k-means problem is defined similarly by using squared distances, i.e., d^2(.,.) instead of d(.,.). The current best approximation guarantee for both the problems is O( ) due to Makarychev and Vakilian [COLT 2021]. In this work, we study the fixed parameter tractability of the problems with respect to parameter k. We design (3+) and (9 + ) approximation algorithms for the socially fair k-median and k-means problems, respectively, in FPT (fixed parameter tractable) time f(k,) n^O(1), where f(k,) = (k/)^O(k) and n = |P F|. Furthermore, we show that if Gap-ETH holds, then better approximation guarantees are not possible in FPT time.

Tasks

Reproductions