|
Published Articles >> Table of Contents >> Abstract
18th Annual IEEE Conference on Computational Complexity (CCC'03)
p. 371
A Strong Inapproximability Gap for a Generalization of Minimum Bisection
Jonas Holmerin, Royal Institute of Technology
Subhash Khot, Princeton University, Princeton, NJ-08544.
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCC.2003.1214436
Send link to a friend
| Abstract |
|
As a problem with similar properties to Minimum Bisection, we consider the following: given a homogeneous system of linear equations over Z_2^{} , with exactly k variables in each equation, find a balanced assignment that minimizes the number of satisfied equations. A balanced assignment is one which contains an equal number of 0s and 1s. When k = 2, this is the Minimum Bisection problem. We consider the case k = 3. In this case, it is NP-complete to determine whether the object function is zero [6], so the problem is not approximable at all. However, we prove that it is NP-hard to determine distinguish between the cases that all but a fraction \varepsilon of the equations can be satisfied and that at least a fraction ¼-\varepsilon of all equations cannot be satisfied. A similar result for Minimum Bisection would imply that the problem is hard to approximate within any constant. For the problem of approximating the maximum number of equations satisfied by a balanced assignment, this implies that the problem is NP-hard to approximate within 4/3-\varepsilon , for any \varepsilon > 0.
|
 Additional Information
|
Citation:
Jonas Holmerin, Subhash Khot,
"A Strong Inapproximability Gap for a Generalization of Minimum Bisection,"
complexity,
p. 371,
18th Annual IEEE Conference on Computational Complexity (CCC'03),
2003
|
|
