Gadgets, Approximation, and Linear Programming (extended abstract).
Luca Trevisan, Gregory B. Sorkin, Madhu Sudan, David P. Williamson · 1996
We present a linear-programming based method for finding "gadgets", i.e., combinatorial structures reducing constraints of one optimization problems 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 [1] on how to prove the optimality of gadgets -- we show how LP duality gives such proofs. The new gadgets improve hardness results for MAX CUT and MAX DICUT, showing that approximating these problems to within factors of 60/61 and 44/45 respectively is NP-hard (improving upon the previous hardness of 71/72 for both problems [1]). We also