Polynomially bounded minimization problems that are hard to approximate
Viggo Kann · 1994
Min PB is the class of minimization problems whose objective functions are bounded by a polynomial in the size of the input. We show that there exist several problems that are Min PB-complete with respect to an approximation preserving reduction. These problems are very hard to approximate; in polynomial time they cannot be approximated within n " for some " ? 0, where n is the size of the input, provided that P 6= NP. In particular, the problem of finding the minimum independent dominating set in a graph, the problem of satisfying a 3-SAT formula setting the least number of variables to one, and the minimum bounded 0 \\Gamma 1 programming problem are shown to be Min PB-complete. We also present a new type of approximation preserving reduction that is designed for problems whose approximability is expressed as a function of some size parameter. Using this reduction we obtain good lower bounds on the approximability of the treated problems.