umu.sePublications
Change search

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
Improved Approximation Algorithms for Maximum Graph Partitioning Problems
Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
Mathematisches Seminar, Christian-Albrechts-Universität Kiel, Germany.
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, p. 348-359Conference paper, Published paper (Refereed)
##### Abstract [en]

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  $k=\frac{n}{2}$  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. p. 348-359
##### Series
Lecture Notes in Computer Science ; Volume 3328
##### National Category
Discrete Mathematics
##### Identifiers
OAI: oai:DiVA.org:umu-84347DiVA, id: diva2:683148
##### Conference
24th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2004)
Available from: 2014-01-02 Created: 2014-01-02 Last updated: 2018-06-08Bibliographically approved

#### Open Access in DiVA

No full text in DiVA

Jäger, Gerold

#### Search in DiVA

Jäger, Gerold
##### On the subject
Discrete Mathematics

urn-nbn

#### Altmetric score

urn-nbn
Total: 100 hits

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf