Abstract
As a problem with similar properties to Minimum Bisection, we consider the following: given a homogeneous system of linear equations over Z2, 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 approximate at all. However, we prove that it is NP-hard to determine distinguish between the cases that all but a fraction ε of the equations can be satisfied and that at least a fraction 1/4 - ε 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 - ε, for any ε > 0.
Original language | English (US) |
---|---|
Title of host publication | Proceedings of the Annual IEEE Conference on Computational Complexity |
Pages | 371-378 |
Number of pages | 8 |
State | Published - 2003 |
Event | 18th Annual IEEE Conference on Computational Complexity - Aarhus, Denmark Duration: Jul 7 2003 → Jul 10 2003 |
Other
Other | 18th Annual IEEE Conference on Computational Complexity |
---|---|
Country/Territory | Denmark |
City | Aarhus |
Period | 7/7/03 → 7/10/03 |
ASJC Scopus subject areas
- Computational Mathematics