ECCC-Report TR03-056https://eccc.weizmann.ac.il/report/2003/056Comments and Revisions published for TR03-056en-usTue, 29 Jul 2003 09:07:46 +0300
Paper TR03-056
| Approximability of Hypergraph Minimum Bisection |
Piotr Berman,
Marek Karpinski
https://eccc.weizmann.ac.il/report/2003/056We prove that the problems of minimum bisection on k-uniform
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 k-uniform 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 2-regular k-uniform hypergraphs are precisely
as hard to approximate as the general minimum bisection problem
on arbitrary graphs for every integer k \geq 3.
Tue, 29 Jul 2003 09:07:46 +0300https://eccc.weizmann.ac.il/report/2003/056