Approximation algorithms for the individually fair k-center with outliers

Lu Han, Dachuan Xu, Yicheng Xu () and Ping Yang
Additional contact information
Lu Han: Beijing University of Posts and Telecommunications
Dachuan Xu: Beijing University of Technology
Yicheng Xu: Chinese Academy of Sciences
Ping Yang: Beijing University of Technology

Journal of Global Optimization, 2023, vol. 87, issue 2, No 13, 603-618

Abstract: Abstract 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 $$\lceil (n-q) / k \rceil $$ ⌈ ( n - q ) / k ⌉ closest neighbors for every served vertex. Because every center serves $$(n -q) / k$$ ( 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 $$\lceil (n - q )/k \rceil _\mathrm{th}$$ ⌈ ( 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.

Keywords: k-center; Individual fairness; Outliers; Approximation algorithm (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01195-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:87:y:2023:i:2:d:10.1007_s10898-022-01195-3

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-022-01195-3

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().