Improved Approximation Algorithms for Maximum Graph Partitioning Problems
2005 (English)In: Journal of combinatorial optimization, ISSN 1382-6905, E-ISSN 1573-2886, Vol. 10, no 2, 133-167 p.Article in journal (Refereed) Published
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 semidefinite 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, Ye, Zhang (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 suboptimal 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.
Place, publisher, year, edition, pages
Kluwer Academic Publishers, 2005. Vol. 10, no 2, 133-167 p.
Maximum Graph Partitioning, Approximation Factor, Semidefinite Programming
IdentifiersURN: urn:nbn:se:umu:diva-83123DOI: 10.1007/s10878-005-2269-7OAI: oai:DiVA.org:umu-83123DiVA: diva2:664943