论文标题
近似加权最低标签$ s $ - $ t $切割问题
Approximating the Weighted Minimum Label $s$-$t$ Cut Problem
论文作者
论文摘要
In the weighted (minimum) {\sf Label $s$-$t$ Cut} problem, we are given a (directed or undirected) graph $G=(V,E)$, a label set $L = \{\ell_1, \ell_2, \dots, \ell_q \}$ with positive label weights $\{w_\ell\}$, a source $s \in v $和v $中的水槽$ t \。 $ g $的每个边缘边缘$ e $都有$ l $的标签$ \ ell（e）$。不同的边缘可能具有相同的标签。问题要求找到最小重量标签子集$ l'$，以便删除所有带有$ l'$ disconnect $ s $和$ t $的标签的边缘。 未加权{\ sf标签$ s $ - $ t $ cut}问题（即每个标签都有单位重量）近似于$ O（n^{2/3}）$，其中$ n $是图形$ g $的顶点。但是，很长一段时间以来，如何在$ o（n）$中近似加权{\ sf标签$ s $ - $ t $ cut}问题是未知的。在本文中，我们为加权{\ sf Label $ s $ - $ t $ cut}的近似算法提供了比率$ o（n^{2/3}）$的问题。该算法的关键点是将标签重量在边缘上解释为其长度和容量的机制。
In the weighted (minimum) {\sf Label $s$-$t$ Cut} problem, we are given a (directed or undirected) graph $G=(V,E)$, a label set $L = \{\ell_1, \ell_2, \dots, \ell_q \}$ with positive label weights $\{w_\ell\}$, a source $s \in V$ and a sink $t \in V$. Each edge edge $e$ of $G$ has a label $\ell(e)$ from $L$. Different edges may have the same label. The problem asks to find a minimum weight label subset $L'$ such that the removal of all edges with labels in $L'$ disconnects $s$ and $t$. The unweighted {\sf Label $s$-$t$ Cut} problem (i.e., every label has a unit weight) can be approximated within $O(n^{2/3})$, where $n$ is the number of vertices of graph $G$. However, it is unknown for a long time how to approximate the weighted {\sf Label $s$-$t$ Cut} problem within $o(n)$. In this paper, we provide an approximation algorithm for the weighted {\sf Label $s$-$t$ Cut} problem with ratio $O(n^{2/3})$. The key point of the algorithm is a mechanism to interpret label weight on an edge as both its length and capacity.
