来水一篇blog…

[link](http://ttic.uchicago.edu/~harry/teaching/pdf/lecture1.pdf)

Min-cut列出方程

$$\min \sum cap(e) \times dist(e)$$
$$dist(v,u) + dist(u, w) \ge dist(v, w)$$
$$dist(s,t) = 1$$
$$dist(v, u) = 0 or 1$$

然后松弛成LP问题

$$\min \sum cap(e) \times dist(e)$$
$$dist(v,u) + dist(u, w) \ge dist(v, w)$$
$$dist(s,t) \ge 1$$
$$dist(v, u) \ge 0$$

问题是松弛成LP问题之后,求出的解可能是分数,如何求出最小割.

方法就是把所有点按照和s点的距离排序,然后枚举前i项形成的点集形成的割,其中最小的就是最小割.

证明在给的pdf链接里面~ 这个方法可以推广到The Multicut Problem,得到一个2-approximation algorithm~

[The Multicut Problem](http://www.cs.cmu.edu/~anupamg/adv-approx/lecture18.pdf)