## 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 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