摘要：We consider the {Requirement Cut} problem, where given an undirected graph G = (V,E) equipped with non-negative edge weights c:E â' R_{+}, and g groups of vertices Xâ,,â¦,X_{g} âS V each equipped with a requirement r_i, the goal is to find a collection of edges F âS E, with total minimum weight, such that once F is removed from G in the resulting graph every X_{i} is broken into at least r_{i} connected components. {Requirement Cut} captures multiple classic cut problems in graphs, e.g., {Multicut}, {Multiway Cut}, {Min k-Cut}, {Steiner k-Cut}, {Steiner Multicut}, and {Multi-Multiway Cut}. Nagarajan and Ravi [Algoritmica`10] presented an approximation of O(log{n}log{R}) for the problem, which was subsequently improved to O(log{g} log{k}) by Gupta, Nagarajan and Ravi [Operations Research Letters`10] (here R = â^' _{i = 1}^g r_i and k = â^ª _{i = 1}^g X_i ). We present an approximation of O(Xlog{R} â^S{log{k}}log{log{k}}) for {Requirement Cut} (here X = max _{i = 1,â¦,g} { X_i }). Our approximation in general is incomparable to the above mentioned previous results, however when all groups are not too large, i.e., X = o((â^S{log{k}}log{g})/(log{R}log{log{k}})), it is better. Our algorithm is based on a new configuration linear programming relaxation for the problem, which is accompanied by a remarkably simple randomized rounding procedure.
