论文标题
$ 2 \ sqrt {k} $ - 最小功率的近似算法$ k $ geded discoint $ st $ - path-
An $2\sqrt{k}$-approximation algorithm for minimum power $k$ edge disjoint $st$ -paths
论文作者
论文摘要
在最小功率网络设计问题中，我们给出了一个无向图$ g =（v，e）$带边缘成本$ \ {c_e：e \ in e \} $。目的是找到一个满足最小功率$ p_c（f）= \ sum_ {v \ in V} \ max \ max \ {c_e：e \ in f \ mbox {in f \ mbox {是} v \} $的规定属性的边缘集合$ f \ subseteq e $。在Min-Power $ K $ EDGE DISCOINT $ ST $ - PATHS问题$ F $应该包含$ K $ EDGE DISCOINT $ ST $ PATHS。这个问题承认了$ k $ - approximation算法，这是一个悬而未决的问题。我们给出了$ 2 \ sqrt {2k} $ - 一般费用的近似算法。
In minimum power network design problems we are given an undirected graph $G=(V,E)$ with edge costs $\{c_e:e \in E\}$. The goal is to find an edge set $F\subseteq E$ that satisfies a prescribed property of minimum power $p_c(F)=\sum_{v \in V} \max \{c_e: e \in F \mbox{ is incident to } v\}$. In the Min-Power $k$ Edge Disjoint $st$-Paths problem $F$ should contains $k$ edge disjoint $st$-paths. The problem admits a $k$-approximation algorithm, and it was an open question whether it admits approximation ratio sublinear in $k$ even for unit costs. We give a $2\sqrt{2k}$-approximation algorithm for general costs.
