Konstantin Makarychev, Warren Schudy, et al.
Random Structures and Algorithms
Given a directed graph G and an arc weight function w : E(G) → ℝ+, the maximum directed cut problem (MAX DICUT) is that of finding a directed cut δ(X) with maximum total weight. In this paper we consider a version of MAX DICUT - MAX DICUT with given sizes of parts or MAX DICUT WITH GSP - whose instance is that of MAX DICUT plus a positive integer p, and it is required to find a directed cut δ(X) having maximum weight over all cuts δ(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 and a remarkable structural property of basic solutions to a linear relaxation. The property is that each component of any basic solution is an element of a set {0, δ, 1/2, 1 - δ, 1}, where δ is a constant that satisfies 0 < δ < 1/2 and is the same for all components.
Konstantin Makarychev, Warren Schudy, et al.
Random Structures and Algorithms
Moshe Lewenstein, Maxim Sviridenko
SODA 1998
Alexander Grigoriev, Maxim Sviridenko, et al.
Mathematical Programming
Nikhil Bansal, Ning Chen, et al.
ACM Transactions on Algorithms