|
Abstract : |
We present a linear programming-based method for finding "gadgets", i.e., combinatorial structures reducing constraints of one optimization problem to constraints of another. A key step in this method is a simple observation which limits the search space to a finite one. Using this new method we present a number of new, computer-constructed gadgets for several different reductions. This method also answers a question posed by Bellare, Goldreich and Sudan [2] of how to prove the optimality of gadgets: LP duality gives such proofs. The new gadgets, when combined with recent results of Hastad [9], improve the known inapproximability results for MAX CUT and MAX DICUT, showing that approximating these problems to within factors of 16=17 + ffl and 12=13 + ffl respectively is NP-hard, for every ffl? 0. Prior to this work, the best known inapproximability thresholds for both problems was 71/72 [2]. Without using the gadgets from this paper, the best possible hardness that would follow from [2, 9] is 18=19. We also use the gadgets to obtain an improved approximation algorithm for MAX 3SAT which guarantees an approximation ratio of:801. This improves upon the previous best bound (implicit from [8, 5]) of:7704. 1, |
