umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
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.
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
Abstract [en]

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.
Keyword [en]
Maximum Graph Partitioning, Approximation Factor, Semidefinite Programming
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-83123DOI: 10.1007/s10878-005-2269-7OAI: oai:DiVA.org:umu-83123DiVA: diva2:664943
Available from: 2013-11-18 Created: 2013-11-18 Last updated: 2017-12-06Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jäger, Gerold
In the same journal
Journal of combinatorial optimization
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 48 hits
CiteExportLink to record
Permanent link

Direct link
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