论文标题
订购$ k $ -Median带有异常值和容忍失误
Ordered $k$-Median with Outliers and Fault-Tolerance
论文作者
论文摘要
在本文中，我们研究了订购$ k $ -Median的两个天然概括，名为强大的订购$ k $ -Median和易于过失的订购$ K $ -Median。在有限的度量空间$（x，d）$的情况下，我们试图打开$ k $设施$ s \ subseteq x $，它诱导服务成本vector $ \ vec {c} = \ {c} = \ {d（j，s）：j \ in x \} $ in x \} $，并最小化订单$ w^^$ w^^$ w^$ w^$ \ fec \ fec。这里$ d（j，s）= \ min_ {i \ in s} d（j，i）$是$ j $与$ s $，$ s $，$ w \ in \ mathbb {r}^{r}^{| x |} $之间的最小距离$ \ vec {c} $。当前的最佳结果是$（5+ε）$ - 近似[CS19]。 我们首先考虑可靠的订购$ k $ -Median，又名订购的$ k $ -Median带有异常值，其中输入由订购的$ k $ -Median实例和参数$ M \ in \ Mathbb {z} _+$组成。目标是打开$ k $ s $ s $，选择$ m $ ublist $ t \ subseteq x $，并将最近的开放设施分配给t $中的每个$ j \。服务成本向量为$ \ vec {c} = \ {d（j，s）：j \ in t \} $中，$ w $ in $ \ mathbb {r}^m $。我们介绍了一个新颖而简单的目标函数，该功能可以实现非线性有序目标的线性分析，应用迭代圆形框架[KLS18]并获得恒定的因子近似。我们使用相同的方法设计了有序的矩阵中值和有序背带中位数的第一个恒定标记。 我们还考虑易于耐药的订购$ k $ -Median，除了与订购的$ k $ -Median相同的输入外，我们还获得了其他客户要求$ \ {r_j \ in \ Mathbb {z} _+：J+：j \ in x \ \} $，并且需要分配$ r_j $开放设施给每个clients $ j $ j $ j \ in x $。 $ j $的服务成本是其指定设施的距离之和，目标是相同的。我们使用新型LP松弛获得了通过新的稀疏技术产生的约束，获得了恒定的近似值。
In this paper, we study two natural generalizations of ordered $k$-median, named robust ordered $k$-median and fault-tolerant ordered $k$-median. In ordered $k$-median, given a finite metric space $(X,d)$, we seek to open $k$ facilities $S\subseteq X$ which induce a service cost vector $\vec{c}=\{d(j,S):j\in X\}$, and minimize the ordered objective $w^\top\vec{c}^\downarrow$. Here $d(j,S)=\min_{i\in S}d(j,i)$ is the minimum distance between $j$ and facilities in $S$, $w\in\mathbb{R}^{|X|}$ is a given non-increasing non-negative vector, and $\vec{c}^\downarrow$ is the non-increasingly sorted version of $\vec{c}$. The current best result is a $(5+ε)$-approximation [CS19]. We first consider robust ordered $k$-median, a.k.a. ordered $k$-median with outliers, where the input consists of an ordered $k$-median instance and parameter $m\in\mathbb{Z}_+$. The goal is to open $k$ facilities $S$, select $m$ clients $T\subseteq X$ and assign the nearest open facility to each $j\in T$. The service cost vector is $\vec{c}=\{d(j,S):j\in T\}$ and $w$ is in $\mathbb{R}^m$. We introduce a novel yet simple objective function that enables linear analysis of the non-linear ordered objective, apply an iterative rounding framework [KLS18] and obtain a constant-factor approximation. We devise the first constant-approximations for ordered matroid median and ordered knapsack median using the same method. We also consider fault-tolerant ordered $k$-median, where besides the same input as ordered $k$-median, we are also given additional client requirements $\{r_j\in\mathbb{Z}_+:j\in X\}$ and need to assign $r_j$ distinct open facilities to each client $j\in X$. The service cost of $j$ is the sum of distances to its assigned facilities, and the objective is the same. We obtain a constant-factor approximation using a novel LP relaxation with constraints created via a new sparsification technique.
