L. Trevisan, G.B. Sorkin, M. Sudan, D.P. Williamson.<br>
<b>Gadgets, Approximation, and Linear Programming.</b><br>
In <i>Proceedings of the 
<a href="http://www.umiacs.umd.edu/events/FOCS96/">37th Symposium on 
Foundations of
Computer Science (FOCS'96)</a></i>, <br>IEEE, 1996.

<dl>




<dt> <b> Abstract </b> <dd>

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  Bellare, Goldreich and Sudan
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).
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 of .7704.


</dl>