论文标题
最小重量成对距离保存器
Minimum Weight Pairwise Distance Preservers
论文作者
论文摘要
在本文中，我们研究了最小重量成对距离保存器（MWPDP）问题。考虑一个积极加权的无向/定向连接图$ g =（v，e，c）$和一个子集$ p $的顶点，也称为需求对。当$ p $相对于$ p $时，仅当每个对$ $（u，w）\ in P $满足$ dist_ {g'}（u，w）（u，w）= dist_ {g}（u，w）$时。在MWPDP问题中，我们的目标是找到有关$ p $的距离保存器的最小权重$ g^*$。在$ p $中，每对之间的最短路径为我们提供了一个微不足道的解决方案，最多的重量为$ u = \ sum _ {（u，v）\ in P} dist_ {g}（u，w）$。随后，我们问我们可以对$ U $进行多少改进。换句话说，我们选择找到一个最大化$ u-c（g^*）$的距离保存器$ g^*$。将此问题表示为成本分享成对距离保存器（CSPDP），该保存器在运输系统的计划和操作中具有多个应用程序。 Chlamtáč等人的CSPDP唯一已知的工作是CSPDP。 （Soda，2017）。该算法适用于未加权的图，并仅当相对于微不足道的解决方案极为稀疏时，才能保证非零目标。我们通过提出$ O（| e |^{1/2+ε}）$ - 加权图中CSPDP的近似算法来解决此问题，该算法以$ o（（（| P | p || e |）^{2.38}（1/ε））运行。此外，我们证明CSPDP至少与$ \ text {label-cover} _ {\ max} $一样困难。这意味着在$ o（| e |^{1/6-ε}）$中，不能在多项式时间内近似CSPDP，除非臭名昭著的困难$ \ text {label-cover} _ {\ max} $有所改善。
In this paper, we study the Minimum Weight Pairwise Distance Preservers (MWPDP) problem. Consider a positively weighted undirected/directed connected graph $G = (V, E, c)$ and a subset $P$ of pairs of vertices, also called demand pairs. A subgraph $G'$ is a distance preserver with respect to $P$ if and only if every pair $(u, w) \in P$ satisfies $dist_{G'} (u, w) = dist_{G}(u, w)$. In MWPDP problem, we aim to find the minimum-weight subgraph $G^*$ that is a distance preserver with respect to $P$. Taking a shortest path between each pair in $P$ gives us a trivial solution with the weight of at most $U=\sum_{(u,v) \in P} dist_{G} (u, w)$. Subsequently, we ask how much improvement we can make upon $U$. In other words, we opt to find a distance preserver $G^*$ that maximizes $U-c(G^*)$. Denote this problem as Cost Sharing Pairwise Distance Preservers (CSPDP), which has several applications in the planning and operations of transportation systems. The only known work that can provide a nontrivial solution for CSPDP is that of Chlamtáč et al. (SODA, 2017). This algorithm works for unweighted graphs and guarantees a non-zero objective only if the optimal solution is extremely sparse with respect to the trivial solution. We address this issue by proposing an $O(|E|^{1/2+ε})$-approximation algorithm for CSPDP in weighted graphs that runs in $O((|P||E|)^{2.38} (1/ε))$ time. Moreover, we prove CSPDP is at least as hard as $\text{LABEL-COVER}_{\max}$. This implies that CSPDP cannot be approximated within $O(|E|^{1/6-ε})$ factor in polynomial time, unless there is an improvement in the notoriously difficult $\text{LABEL-COVER}_{\max}$.
