Gadgets, Approximation, and Linear Programming
Luca Trevisan, Gregory B. Sorkin, Madhu Sudan et al. · SIAM Journal on Computing · 2000
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 [SIAM J. Comput., 27 (1998), pp. 804--915] of how to prove the optimality of gadgets: linear programming duality gives such proofs. The new gadgets, when combined with recent results of Håstad [ Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 1--10], improve the known inapproximability results for MAX CUT and MAX DICUT, showing that approximating these problems to within factors of $16/17 + ε$ and $12/13+ ε,$ respectively, is NP-hard for every ε > 0. Prior to this work, the best-known inapproximability thresholds for both problems were 71/72 (M. Bellare, O. Goldreich, and M. Sudan [ SIAM J. Comput., 27 (1998), pp. 804--915]). Without using the gadgets from this paper, the best possible hardness that would follow from Bellare, Goldreich, and Sudan and Håstad is 18/19. We also use the gadgets to obtain an improved approximation algorithm for MAX3 SAT which guarantees an approximation ratio of .801. This improves upon the previous best bound (implicit from M. X. Goemans and D. P. Williamson [J. ACM, 42 (1995), pp. 1115--1145]; U. Feige and M. X. Goemans [Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182--189]) of .7704.
Cited by 199 works. doi:10.1137/s0097539797328847
Authors
References
- Reducibility among Combinatorial Problems
- Some simplified NP-complete graph problems
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Optimization, approximation, and complexity classes
- Some optimal inapproximability results
- Proof verification and the hardness of approximation problems
- On the Approximation of Maximum Satisfiability
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT
- New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem