Improved Approximation Algorithms for Maximum Graph Partitioning Problems
2004 (English)In: Proceedings of 24th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2004) / [ed] P.K. Lodaya and M. Mahajan, Berlin-Heidelberg: Springer Berlin/Heidelberg, 2004, 348-359 p.Conference paper (Refereed)
In this paper we improve the analysis of approximation algorithms based on semidefinite programming for the maximum graph partitioning problems MAX-k-CUT, MAX-k-UNCUT, MAX-k-DIRECTEDCUT, MAX-k-DIRECTED-UNCUT, MAX-k-DENSE-SUBGRAPH, and MAX-k-VERTEX-COVER. It was observed by Han, Ye, Zhang (2002) and Halperin, Zwick (2002) that a parameter-driven random hyperplane can lead to better approximation factors than obtained by Goemans and Williamson (1994). Halperin and Zwick could describe the approximation factors by a mathematical optimization problem for the above problems for and found a choice of parameters in a heuristic way. The innovation of this paper is twofold. First, we generalize the algorithm of Halperin and Zwick to cover all cases of k, adding some algorithmic features. The hard work is to show that this leads to a mathematical optimization problem for an optimal choice of parameters. Secondly, as a key-step of this paper we prove that a sub-optimal set of parameters is determined by a linear program. Its optimal solution computed by CPLEX leads to the desired improvements. In this fashion a more systematic analysis of the semidefinite relaxation scheme is obtained which leaves room for further improvements.
Place, publisher, year, edition, pages
Berlin-Heidelberg: Springer Berlin/Heidelberg, 2004. 348-359 p.
, Lecture Notes in Computer Science, Volume 3328
IdentifiersURN: urn:nbn:se:umu:diva-84347OAI: oai:DiVA.org:umu-84347DiVA: diva2:683148
24th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2004)