A strong inapproximability gap for a generalization of minimum bisection

Jonas Holmerin, Subhash Khot

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings of the Annual IEEE Conference on Computational Complexity
Pages371-378
Number of pages8
StatePublished - 2003
Event18th Annual IEEE Conference on Computational Complexity - Aarhus, Denmark
Duration: Jul 7 2003Jul 10 2003

Other

Other18th Annual IEEE Conference on Computational Complexity
Country/TerritoryDenmark
CityAarhus
Period7/7/037/10/03

ASJC Scopus subject areas

  • Computational Mathematics

Fingerprint

Dive into the research topics of 'A strong inapproximability gap for a generalization of minimum bisection'. Together they form a unique fingerprint.

Cite this