Improved approximation algorithms for maximum graph partitioning problems

We consider the design of approximation algorithms for a number of maximum graph partitioning problems, among others MAX-k-CUT, MAX-k-DENSE-SUBGRAPH, and MAX-k-DIRECTED-UNCUT. We present a new version of the semidefnite relaxation scheme along with a better analysis, extending work of Halperin and Zwick (2002). This leads to an improvement over known approximation factors for such problems. The key to the improvement is the following new technique: It was already observed by Han et al. (2002) that a parameter-driven choice of the random hyperplane can lead to better approximation factors than obtained by Goemans and Williamson (1995). But it remained difficult to find a "good" set of parameters. In this paper, we analyze random hyperplanes depending on several new parameters. We prove that a sub-optimal choice of these parameters can be obtained by the solution of a linear program which leads to the desired improvement of the approximation factors. In this fashion a more systematic analysis of the semidefinite relaxation scheme is obtained.