Harmonic algorithm for 3-dimensional strip packing problem
Nikhil Bansal, Xin Han, et al.
SODA 2007
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.
Nikhil Bansal, Xin Han, et al.
SODA 2007
Nikhil Bansal, Maxim Sviridenko
STOC 2006
Nikhil Bansal, Maxim Sviridenko
SODA 2004
Konstantin Makarychev, Warren Schudy, et al.
SODA 2012