Autor(en): | Dolezal, Oliver Hofmeister, Thomas Lefmann, Hanno |
Titel: | A Comparison of Approximation Algorithms for the MaxCut-Problem |
Sprache (ISO): | en |
Zusammenfassung: | In this paper we compare, from a practical point of view, approximation algorithms for the problem MaxCut . For this problem, we are given an undirected graph G = (V;E) with vertex set V and edge set E, and we are looking for a partition V = V1 [ V2 with V1 \ V2 = 0 of the vertex set which maximizes the number of edges e 2 E which have one endpoint in V1 and the other in V2 . The investigated algorithms include semidefinite programming, a random strategy, genetic algorithms, two combinatorial algorithms and a divide-and-conquer strategy. |
URI: | http://hdl.handle.net/2003/5366 http://dx.doi.org/10.17877/DE290R-5013 |
Erscheinungsdatum: | 2001-10-16 |
Provinienz: | Universität Dortmund |
Enthalten in den Sammlungen: | Sonderforschungsbereich (SFB) 531 |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
ci57.pdf | DNB | 298.1 kB | Adobe PDF | Öffnen/Anzeigen |
ci57.ps | 391.51 kB | Postscript | Öffnen/Anzeigen |
Diese Ressource ist urheberrechtlich geschützt. |
Diese Ressource ist urheberrechtlich geschützt. rightsstatements.org