Optimization of Gadgets
One application of gadgets is in proving hardness of approximation results, by reducing a problem that is known to be hard to approximate to another problem whose hardness is to be proven. In this application, one typically has a family of instances of the first problem in which there is a gap in the objective function values, and in which it is hard to determine whether a given instance has an objective function that is on the low side or on the high side of the gap. The reductions used in these proofs, and the gadgets used in the reductions, must preserve the existence of this gap, and the strength of the inapproximability result derived from the reduction will depend on how well the gap is preserved.
Trevisan et al. (2000) formalize the problem of finding gap-preserving gadgets, for families of constraint satisfaction problems in which the goal is to maximize the number of satisfied constraints. They give as an example a reduction from 3-satisfiability to 2-satisfiability by Garey, Johnson & Stockmeyer (1976), in which the gadget representing a 3-SAT clause consists of ten 2-SAT clauses, and in which a truth assignment that satisfies 3-SAT clause also satisfies at least seven clauses in the gadget, while a truth assignment that fails to satisfy a 3-SAT clause also fails to satisfy more than six clauses of the gadget. Using this gadget, and the fact that (unless P = NP) there is no polynomial-time approximation scheme for maximizing the number of 3-SAT clauses that a truth assignment satisfies, it can be shown that there is similarly no approximation scheme for MAX 2-SAT.
Trevisan et al. show that, in many cases of the constraint satisfaction problems they study, the gadgets leading to the strongest possible inapproximability results may be constructed automatically, as the solution to a linear programming problem. The same gadget-based reductions may also be used in the other direction, to transfer approximation algorithms from easier problems to harder problems. For instance, Trevisan et al. provide an optimal gadget for reducing 3-SAT to a weighted variant of 2-SAT (consisting of seven weighted 2-SAT clauses) that is stronger than the one by Garey, Johnson & Stockmeyer (1976); using it, together with known semidefinite programming approximation algorithms for MAX 2-SAT, they provide an approximation algorithm for MAX 3-SAT with approximation ratio 0.801, better than previously known algorithms.
Read more about this topic: Gadget (computer Science)
Famous quotes containing the word gadgets:
“Man is by nature a pragmatic materialist, a mechanic, a lover of gadgets and gadgetry; and these are qualities that characterize the “establishment” which regulates modern society: pragmatism, materialism, mechanization, and gadgetry. Woman, on the other hand, is a practical idealist, a humanitarian with a strong sense of noblesse oblige, an altruist rather than a capitalist.”
—Elizabeth Gould Davis (b. 1910)