标题：A new approximation algorithm for the unbalanced Min s-t Cut problem
作者机构：[Zhang, Peng] Shandong Univ, Sch Comp Sci & Technol, Jinan, Peoples R China.
会议名称：20th International Conference on Computing and Combinatorics (COCOON)
会议日期：AUG 04-06, 2014
来源：THEORETICAL COMPUTER SCIENCE
关键词：Unbalanced cut; MM s-t cut; Approximation algorithm; Linear programming;; Network community
摘要：Being the unbalanced version of the famous Min s-t Cut problem, the Min k-Size s-t Cut problem asks to find a k-size s-t cut with the minimum capacity, where a k-size s-t cut means an s-t cut with its s-side having size at most k. This problem is fundamental and has extensive applications, especially in community identification in social and information networks. It is known that the Min k-Size s-t Cut problem is NP-hard and can be approximated within O (logn), where n is the number of vertices in the input graph. In this paper, we give a new approximation algorithm for the Min k-Size s-t Cut problem based on the parametric flow technique. The algorithm is very simple and has only three lines to state. Its approximation ratio is k+1/K+1-k*, where k* is the size of the s-side of an optimal solution. (C) 2015 Elsevier B.V. All rights reserved.