论文标题
FPT近似受约束度量$ k $ -Median/平均值
FPT Approximation for Constrained Metric $k$-Median/Means
论文作者
论文摘要
公制空间$（\ MATHCAL {x}，d）$上的度量$ k $ -Median问题定义如下：给定设施位置的$ l \ subseteq \ subseteq \ subseteq \ subseteq \ subseteq \ Mathcal {x} $ AS $φ（f，c）\ equiv \ sum_ {x \ in c} \ min_ {f \ in f} d（x，f）$，被最小化。公制$ k $ -MEANS问题的定义类似地使用平方距离。在许多应用中，任何解决方案都需要满足的其他限制。这引起了该问题的不同约束版本，例如$ r $ - 易于故障，宽敞的$ k $ -mean -means/$ k $ -Median问题。令人惊讶的是，对于许多这些受约束的问题，尚无恒定的附属算法。我们为一系列受约束的$ k $ -Median/含义问题提供了FPT算法，并具有持续近似保证。对于某些受约束的问题，我们的问题是第一个常数因子近似算法，而对于其他因素近似算法，我们改进或匹配以前作品的近似保证。我们在Ding和Xu的统一框架内工作，使我们能够同时获得一系列受约束问题的算法。特别是，我们获得了$（3+ \ varepsilon）$ - 近似值和$（9+ \ varepsilon）$ - 分别在fpt时间内分别用于$ k $ -Median和$ k $ -MEANS的约束版本。在$ K $ -Median/Means问题的许多实际设置中，允许在任何客户位置（即$ C \ subseteq l $）打开一个设施。对于这种特殊情况，我们的算法给出了$（2+ \ varepsilon）$ - 近似值和$（4+ \ varepsilon）$ - 分别在$ k $ -Median和$ k $ -means的约束版本中分别在fpt时间内。由于我们的算法基于简单的采样技术，因此也可以将其转换为恒定的日志空间流算法。
The Metric $k$-median problem over a metric space $(\mathcal{X}, d)$ is defined as follows: given a set $L \subseteq \mathcal{X}$ of facility locations and a set $C \subseteq \mathcal{X}$ of clients, open a set $F \subseteq L$ of $k$ facilities such that the total service cost, defined as $Φ(F, C) \equiv \sum_{x \in C} \min_{f \in F} d(x, f)$, is minimised. The metric $k$-means problem is defined similarly using squared distances. In many applications there are additional constraints that any solution needs to satisfy. This gives rise to different constrained versions of the problem such as $r$-gather, fault-tolerant, outlier $k$-means/$k$-median problem. Surprisingly, for many of these constrained problems, no constant-approximation algorithm is known. We give FPT algorithms with constant approximation guarantee for a range of constrained $k$-median/means problems. For some of the constrained problems, ours is the first constant factor approximation algorithm whereas for others, we improve or match the approximation guarantee of previous works. We work within the unified framework of Ding and Xu that allows us to simultaneously obtain algorithms for a range of constrained problems. In particular, we obtain a $(3+\varepsilon)$-approximation and $(9+\varepsilon)$-approximation for the constrained versions of the $k$-median and $k$-means problem respectively in FPT time. In many practical settings of the $k$-median/means problem, one is allowed to open a facility at any client location, i.e., $C \subseteq L$. For this special case, our algorithm gives a $(2+\varepsilon)$-approximation and $(4+\varepsilon)$-approximation for the constrained versions of $k$-median and $k$-means problem respectively in FPT time. Since our algorithm is based on simple sampling technique, it can also be converted to a constant-pass log-space streaming algorithm.
