Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2003 Copyright 2003 University of Bonn, Department of Computer Science, Abt. V
85251

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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V