Header menu link for other important links
X
Improved NP-inapproximability for 2-variable linear equations
Published in Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
2015
Volume: 40
   
Pages: 341 - 360
Abstract
An instance of the 2-Lin(2) problem is a system of equations of the form "xi + xj = b (mod 2)". Given such a system in which it's possible to satisfy all but an C ε fraction of the equations, we show it is NP-hard to satisfy all but a Cε fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < ε ≤ 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique-Games problem, and it also holds for the special case of Max-Cut. The precise factor 11 8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitation on gadget reductions was known. © Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright.
About the journal
JournalLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISSN18688969
Open AccessNo
Concepts (15)
  •  related image
    Approximation algorithms
  •  related image
    Combinatorial optimization
  •  related image
    Hardness
  •  related image
    Linear equations
  •  related image
    Linear programming
  •  related image
    Random processes
  •  related image
    Approximability
  •  related image
    GADGET
  •  related image
    HARDNESS FACTOR
  •  related image
    INAPPROXIMABILITY
  •  related image
    Inherent limitations
  •  related image
    Np-hardness
  •  related image
    System of equations
  •  related image
    UNIQUE GAMES
  •  related image
    Optimization