Approximation algorithms for the individually fair k-center with outliers

In this paper, we propose and investigate the individually fair k-center with outliers (IFkCO). In the IFkCO, we are given an n-sized vertex set in a metric space, as well as integers k and q. At most k vertices can be selected as the centers and at most q vertices can be selected as the outliers. The centers are selected to serve all the not-an-outlier (i.e., served) vertices. The so-called individual fairness constraint restricts that every served vertex must have a selected center not too far way. More precisely, it is supposed that there exists at least one center among its [(n - q)/k] closest neighbors for every served vertex. Because every center serves (n - q)/k vertices on the average. The objective is to select centers and outliers, assign every served vertex to some center, such that the maximum fairness ratio over all served vertices is minimized, where the fairness ratio of a vertex is defined as the ratio between its distance with the assigned center and its distance with a [(n - q)/k](th) closest neighbor. As our main contribution, a 4-approximation algorithm is presented, based on which we develop an improved algorithm from a practical perspective. Extensive experiment results on both synthetic datasets and real-world datasets are presented to illustrate the effectiveness of the proposed algorithms.

Automated summary

This paper investigates the individually fair k-center with outliers (IFkCO) problem. A 4-approximation algorithm is proposed and an improved algorithm is developed from a practical perspective. Extensive experiment results are presented to demonstrate the effectiveness of the proposed algorithms.