Authors: Dolezal, Oliver
Hofmeister, Thomas
Lefmann, Hanno
Title: A Comparison of Approximation Algorithms for the MaxCut-Problem
Language (ISO): en
Abstract: 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.
Issue Date: 2001-10-16
Provenance: Universität Dortmund
Appears in Collections:Sonderforschungsbereich (SFB) 531

Files in This Item:
File Description SizeFormat 
ci57.pdfDNB298.1 kBAdobe PDFView/Open
ci57.ps391.51 kBPostscriptView/Open

This item is protected by original copyright

All resources in the repository are protected by copyright.