A 0.5-approximation algorithm for MAX DICUT with given sizes of parts

Given a directed graph G and an arc weight function w : E(G) --> R+, the ma ximum directed cut problem (MAX DICUT) is that of finding a directed cut de lta (X) with maximum total weight. In this paper we consider a version of M AX DICUT-MAX DICUT with given sizes of parts or MAX DICUT WITH GSP-whose in stance is that of MAX DICUT plus a positive integer p, and it is required t o nd a directed cut delta (X) having maximum weight over all cuts delta (X) with |X| = p. Our main result is a 0.5-approximation algorithm for solving the problem. The algorithm is based on a tricky application of the pipage rounding technique developed in some earlier papers by two of the authors a nd a remarkable structural property of basic solutions to a linear relaxati on. The property is that each component of any basic solution is an element of a set {0,delta ,1/2,1-delta ,1}, where delta is a constant that satisfi es 0 < <delta> < 1/2 and is the same for all components.