×

Polynomially bounded minimization problems that are hard to approximate. (English) Zbl 0817.68082

Summary: 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^ \varepsilon\) for some \(\varepsilon > 0\), where \(n\) is the size of the input, provided that \(P \neq 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-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.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite