
Universität Bonn > Institut für Informatik > Abteilung V  
CSAPXReports 2003  Copyright 2003 Universität Bonn, Institut für Informatik, Abt. V  
8992 29.07.2003 
Approximability of Hypergraph Minimum Bisection
Piotr Berman and Marek Karpinski [Download PostScript] [Download PDF] We prove that the problems of minimum bisection on kuniform hypergraphs are almost exactly as hard to approximate, up to the factor k/3, as the problem of minimum bisection on graphs. On a positive side, our argument gives also the first approximation algorithms for the problem of minimum bisection on kuniform hypergraphs, for every integer k, of a comparable guarantee as for the minimum bisection on graphs. Moreover, we prove that the problems of minimum bisection on very sparse 2regular kuniform hypergraphs are precisely as hard to approximate as the general minimum bisection problem on arbitrary graphs for every integer k >= 3. 

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