论文标题
与离群值近似单独的k-center
Approximate the individually fair k-center with outliers
论文作者
论文摘要
在本文中，我们提出并调查具有异常值（如果$ k $ co）的单独公平$ k $中心。在IF $ K $ CO中，我们将在公制空间中为我们提供了$ n $尺寸的顶点，以及整数$ k $和$ q $。最多可以作为中心选择$ k $的顶点，最多只能选择$ q $ $的顶点作为异常值。选择中心以服务所有不利的（即服务）顶点。所谓的个人公平限制限制了每个服务顶点必须具有所选的中心不远的方式。更确切地说，据推测，在其$ \ lceil（n-q） / k \ rceil $ $最接近的邻居中至少存在一个中心。因为每个中心平均提供$（N-Q） / K $顶点。目的是选择中心和离群值，将每个服务的顶点分配到某个中心，以最大程度地降低所有服务顶点的最大公平比率，在所有服务顶点中，顶点的公平比率定义为与分配的中心的距离与$ \ lceil（n -q）/k \ rceil _ rceil _ flood的距离之间的比率。作为我们的主要贡献，提出了一种4-辅助算法，基于该算法，我们从实际的角度开发了改进的算法。
In this paper, we propose and investigate the individually fair $k$-center with outliers (IF$k$CO). In the IF$k$CO, 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$ 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, so as to minimize the maximum fairness ratio over all served vertices, 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_{\rm 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.
