Efficient approximation schemes for uniform-cost clustering problems in planar graphs
Efficient approximation schemes for uniform-cost clustering problems in planar graphs
复制标题
平面图中均匀成本聚类问题的高效近似方案
DOI：
10.4230/lipics.esa.2019.33
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Michal Pilipczuk
中科院分区：
文献类型：
--
作者：
Vincent Cohen;Marcin Pilipczuk;Michal Pilipczuk
我们考虑平面图上的$k$-中值问题：给定一个边加权平面图$G$，一个客户集$C\subseteq V(G)$，一个设施集$F\subseteq V(G)$，以及一个整数参数$k$，任务是找到一个至多$k$个设施集，它们的开通使客户的总连接成本最小，其中每个客户贡献到最近开放设施的距离的费用。我们给出了这一问题的两个新的近似格式：--FPT近似格式：对于任何$\epsilon；>0$，在时间$2^{O(k\epsilon^{-3}\log(k\epsilon^{-1}))}\CDOT n^{O(1)}$我们可以计算出一个解
(1)连接成本最高为最优的$(1+\epsilon)$，概率很大。--有效的双准则近似格式：对于任何$\epsilon；0$，时间$2^{O(\epsilon^{-5}\log(\epsilon^{-1}))}\cot n^{O(1)}$我们最多可以计算一组$(1+\epsilon)k$设施
(2)其开通成本最高为$(1+1)$，是最多开通$k$设施的最优连接成本的1倍，概率很大。
作为第二个结果的直接推论，我们得到了平面图上具有相同运行时间的一致设施位置的一个EPTAS。
我们的主要技术工具是构造平面图中$k$-中值的“设施核重置”：我们证明了在多项式时间内可以计算出$k\cdot(\logn/\epsilon)^{O(\epsilon^{-3})}$的设施子集$F_0\subseteq F$，并且保证在$F_0$中包含$(1+\epsilon)$-近似解。
We consider the $k$-Median problem on planar graphs: given an edge-weighted planar graph $G$, a set of clients $C \subseteq V(G)$, a set of facilities $F \subseteq V(G)$, and an integer parameter $k$, the task is to find a set of at most $k$ facilities whose opening minimizes the total connection cost of clients, where each client contributes to the cost with the distance to the closest open facility. We give two new approximation schemes for this problem: -- FPT Approximation Scheme: for any $\epsilon>0$, in time $2^{O(k\epsilon^{-3}\log (k\epsilon^{-1}))}\cdot n^{O(1)}$ we can compute a solution that
(1) has connection cost at most $(1+\epsilon)$ times the optimum, with high probability. -- Efficient Bicriteria Approximation Scheme: for any $\epsilon>0$, in time $2^{O(\epsilon^{-5}\log (\epsilon^{-1}))}\cdot n^{O(1)}$ we can compute a set of at most $(1+\epsilon)k$ facilities
(2) whose opening yields connection cost at most $(1+\epsilon)$ times the optimum connection cost for opening at most $k$ facilities, with high probability.
As a direct corollary of the second result we obtain an EPTAS for the Uniform Facility Location on planar graphs, with same running time.
Our main technical tool is a new construction of a "coreset for facilities" for $k$-Median in planar graphs: we show that in polynomial time one can compute a subset of facilities $F_0\subseteq F$ of size $k\cdot (\log n/\epsilon)^{O(\epsilon^{-3})}$ with a guarantee that there is a $(1+\epsilon)$-approximate solution contained in $F_0$.