TR02-046 | 16th July 2002 00:00
On Approximability of Minimum Bisection Problem
TR02-046
Authors:
Marek Karpinski
Publication: 17th July 2002 08:17
Downloads: 4551
Keywords:
Approximation Algorithms,
Approximation Hardness,
Dense Instances,
MAX-BISECTION,
Metric Spaces,
MIN-2SAT,
MIN-BISECTION,
MIN-CLUSTERING,
NP-hardness,
Planar Instances,
Polynomial Time Approximation Schemes,
Sparse Instances
Abstract:
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.
