论文标题
在固定的$ k $ - 连接性问题上
On rooted $k$-connectivity problems in quasi-bipartite digraphs
论文作者
论文摘要
我们考虑定向的最小成本子集$ k $ - 边缘连接问题：给定digraph $ g =（v，e）$带有边缘成本，$ t \ subseteq v $ terminals的终端$ r $，root node $ r $，integer $ k $，一个$ k $ k $ k $ k $ k $ k $ k $ k $ k $ k $ k $ k $ t $ k $ rt $ rt cost $ rt-rt cypt y rt rt-rt cyb y rt rt。当$ t $中的每个优势都在弗兰克（Frank [Dipte）[dipt）中承认多项式时间算法时，这是一个算法。应用。数学。 157（6）：1242-1254，2009]，当所有正成本边缘发生到$ r $的情况下，相当于$ k $ - 万月的问题。 Chan，Laekhanukit，Wei和Zhang [大约/随机，63：1-63：20，2020]给出了一个基于LP的$ O（\ ln k \ ln | t |）$ - quasi-bipartite实例的近似算法，当$ g $中的每个边缘中的每一个边缘都有$ g $（$ g $ tail tail of tail of tail of tail of tail of tail）$ t（tail或head tail tail tail tail of tail of tail（tail）$ t tail（$ thep）。我们给出了一个简单的组合算法，其比率相同，以通过最低成本边缘设置覆盖任意$ t $ to的超模型设置功能的更一般性问题，而对于只有每个正成本边缘在$ t \ t \ cup \ cup \ {r \ \} $中都结束时的情况。
We consider the directed Min-Cost Rooted Subset $k$-Edge-Connection problem: given a digraph $G=(V,E)$ with edge costs, a set $T \subseteq V$ of terminals, a root node $r$, and an integer $k$, find a min-cost subgraph of $G$ that contains $k$ edge disjoint $rt$-paths for all $t \in T$. The case when every edge of positive cost has head in $T$ admits a polynomial time algorithm due to Frank [Discret. Appl. Math. 157(6):1242-1254, 2009], and the case when all positive cost edges are incident to $r$ is equivalent to the $k$-Multicover problem. Chan, Laekhanukit, Wei, and Zhang [APPROX/RANDOM, 63:1-63:20, 2020] gave an LP-based $O(\ln k \ln |T|)$-approximation algorithm for quasi-bipartite instances, when every edge in $G$ has an end (tail or head) in $T \cup \{r\}$. We give a simple combinatorial algorithm with the same ratio for a more general problem of covering an arbitrary $T$-intersecting supermodular set function by a minimum cost edge set, and for the case when only every positive cost edge has an end in $T \cup \{r\}$.
