AbstractMIN 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 nepsilon for some epsilon > 0, where n is the size of the input, provided that P /= 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.
Categories and Subject Descriptors: F.1.3 [Computation by Abstract Devices]: Complexity Classes; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: approximation, reducibility, completeness, graph problems
Selected papers that cite this one
- Edoardo Amaldi and Viggo Kann. On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems. Theoretical Computer Science, 209(1-2):237-260, 6 December 1998.
- Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, and Richard E. Stearns. The complexity of planar counting problems. SIAM Journal on Computing, 27(4):1142-1167, August 1998.
- P. Jonsson. Near-optimal nonapproximability results for some NPO PB-complete problems. Information Processing Letters, 68(5):249-253, 15 December 1998.
Selected references
- Oscar H. Ibarra and Chul E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4):463-468, October 1975.