Revisiting Priority k-Center: Fairness and Outliers
Monday, May 17, 2021, 11:00 am-12:00 pm 
Abstract
Clustering problems are well-studied unsupervised learning problems that are widely used in practice. Recently, there has been a trend in defining fairness in clustering and devising fair clustering algorithms. In this talk we focus on the k-center objective: Given a set of points in the metric space and a parameter k, cover the points using k balls with minimum radius. We discuss two definitions of fair k-center, individual fairness (introduced by Jung et al. FORC '20) and the lottery model (introduced by Harris et. al. NeurIPS '18) and show how they are connected to a previously studied problem called the priority k-center problem (Plesnik '87). In this problem, each point v comes with a radius r_v and demands a center to be opened within this radius. This has a 2-approximation due to Plesnki, that is, an algorithm that outputs a solution where each point v has a center at distance at most 2r_v.
Our main contribution is approximating priority k-center with outliers: where the algorithm is allowed to discard a certain number of points before clustering. We even take a step further and consider more general constraints on the set of centers that can be opened. For example, matroid constraints (open centers are independent in a given matroid) or knapsack constraints (each center has a cost and the solution has to fit in a given budget). This framework reproduces Harris et. al.’s approximation for the chance k-coverage problem and gives the first approximation for matroid and knapsack versions of the problem.
This is a joint work with Tanvi Bajpai, Deeparnab Chakrabarty, and Chandra Chekuri.
Passcode: FairAI-T9
This talk is organized by Leonidas Tsepenekas