Approximation algorithms for MAX RES CUT with limited unbalanced constraints

摘要

Two kinds of MAX RES CUT problems, the MAX s-t CUT and the MAX s-t-v CUT, with limited unbalanced constraints are considered. Approximation algorithms used in Frieze and Jerrum (Integer Programming and Combinatorial Optimization, vol. 920, pp. 1-13, Springer, Berlin, 1995), Galbiati and Maffioli (Theor. Comput. Sci. 385:78-87, 2007), Han et al. (Math. Program. Ser. B 92:509-535, 2002) and Ye (Math. Programm. 90:101-111, 2001) are extended to the two MAX RES CUT problems. A special matrix P is constructed by which it can ensure that the given nodes s,t are feasible to equality constraints with probability one for the MAX s-t CUT and s,t,v are feasible to equality constraints with at least probability 0.912 for the MAX s-t-v CUT. A fussy greedy sizing-adjusted procedure is then proposed to confirm that the round solution is feasible for all constraints. We find these extensions are nontrivial and some interesting results about performance ratio are obtained for the MAX RES CUT problem with limited unbalanced constraints.