期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2003
卷号：2003
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We 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.
关键词：Approximation Algorithms , Approximation Hardness , Approximation Ratios , Average Case Complexity. , Hypergraphs , Minimum Bisection , Weighted Graphs
