论文部分内容阅读
We investigate the unbalanced cut problems.A cut (A;B) is called unbalanced if the size of its smaller side is at most k (called k-size) or exactly k (called Ek-size),where k is an input parameter.An s-t cut (A;B) is called unbalanced if its s-side is of k-size or Ek-size.We consider three types of unbalanced cut problems,in which the quality of a cut is measured with respect to the capacity,the sparsity,and the conductance,respectively.We show that even if the input graph is restricted to be a tree,the Ek-Sparsest Cut problem (to find an Ek-size cut with the minimum sparsity) is still NP-hard.We give a bicriteria approximation algorithm for the k-Sparsest Cut problem (to find a k-size cut with the minimum sparsity),which outputs a cut whose sparsity is at most O(log n) times the optimum and whose smaller side has size at most O(log n)k.As a consequence,this leads to a (O(log n);O(log n))-approximation algorithm for the Min k-Conductance problem (to find a k-size cut with the minimum conductance).We also prove that the Min k-Size s-t Cut problem is NP-hard and give an O(log n) approximation algorithm for it.The approximation ratios given in this paper for k-Sparsest Cut,Min k-Conductance,and Min k-Size s-t Cut are the best ratios currently known for the corresponding problems.