Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2003 Copyright 2003 Universität Bonn, Institut für Informatik, Abt. V
8989

21.05.2003

On Approximability of Minimum Bisection and Related Partition Problems
Marek Karpinski
[Download PostScript] [Download PDF]

We survey some recent results on the complexity of computing approximate solutions for instances of the Minimum Bisection problem and formulate some intriguing and still open questions about the approximability status of that problem. Some connections to other optimization problems are also indicated.

Last Change: 11/05/14 at 10:27:51
 English
Universität Bonn -> Institut für Informatik -> Abteilung V