Authors: Bin Fu and Richard Beigel
Abstract: We develop a general technique for constructing molecular-based approximation algorithms for NP optimization problems. Our algorithms exhibit a useful volume-accuracy tradeoff. In particular we solve the Covering problem of Hochbaum and Maass using polynomial time and O(l² (log l) n² (n(n-1) choose l²/2)) volume with error ratio (1+1/l)². We also present the first candidate for a problem that can be solved more efficiently with the Amplify operation than without.