算法高级教程3.9hardnessofapproximation.pptVIP

PROOF Let ∏ be an NP-hard polynomially bounded maximization problem (the minimization case would lead to a similar proof). Suppose we had a FPTAS A for ∏ which, for any instance I and for any rational ε0, runs in time bounded by P′(|I|,1/ε) for a suitable polynomial P′. Since ∏ is polynomially bounded, there exists a polynomial P such that, for any instance I, A(I) ≤ P(|I|). Let ε = 1/P(|I|), since A is a FPTAS, we have that That is, where the last inequality is due to the fact that OPT(I) ≤P(|I|). From the integrality constraint on the objective function value, it follows that A(I) is an optimal solution. Since the running time of A is bounded by P′ (|I|, 1/ε), we have that ∏ is solvable in polynomial time. From the NP-hardness of ∏, the theorem thus follows. Strong NP-hardness and FPTAS’s A problem ∏ is said to be strongly NP-hard if every problem in NP can be polynomially reduced to ∏ such that the numbers in this new reduction are all written in unary. A strongly NP-hard problem cannot have a pseudo-polynomial time algorithm, assuming P≠NP. Theorem Let P be a polynomial and ∏ be an NP-hard minimization problem such that the objective function f is integer valued and on any instance I, OPT(I) P(|Iu|). If ∏ admits an FPTAS, then it also admits a pseudo-polynomial time algorithm. Proof Suppose there is an FPTAS for whose running time on instance I and error parameter is P′(|I|, 1/ε), where P′ is a polynomial. If we let ε = 1/P(|Iu|), running the FPTAS will give us a solution that is at most: (1+ε)OPT(I) OPT(I) + P(| Iu |) = OPT(I) +1 since by assumption OPT(I) P(| Iu |). This result implies that the FPTAS will have to yield the optimal solution. The running time of the FPTAS is then P′(|I|, 1/ε) = P′(|I|, P(| Iu |)), a polynomial in |Iu|, yielding a pseudo-polynomial time algorithm for ∏. Corollary Let ∏ be an NP-hard optimization problem satisfying the restrictions of the above theorem, If ∏ is strongly NP-hard, then ∏ does not admit an FPTAS,