8
$\begingroup$

I understood that we can apply FPTAS to the weak NP problems like 0-1 knapsack.

But why we cant apply the same principle to the strong NP problems like bin packing? I also checked wiki page about the same but understood very less.

$\endgroup$
1

2 Answers 2

10
$\begingroup$

If there were an FPTAS for some strongly NP-complete problems then you could use the FPTAS to solve them in polytime. Consider for example bin packing. If the solution is of order $V$, then the input size is of order $V$. Therefore a $1-1/V$-approximation can be achieved in polytime, and since the answer is an integer, such an approximation actually gives the optimal answer. I'll let you work out the details.

$\endgroup$
6
  • 1
    $\begingroup$ Why does this provide the optimal answer due to the fact that the answers are integers? Is it related to rounding? as in 1 - 1/V where 1/V is <= 0.5 (if V is >= 2) and thus it gets rounded down? $\endgroup$
    – Gooey
    Oct 8, 2014 at 20:27
  • 1
    $\begingroup$ Suppose that the answer is $1$ or $2$ and you have an approximation algorithm with ratio better than a $1/2$. If the result is larger than $1$ then it has to be $2$, and otherwise it is $1$. Now generalize. $\endgroup$ Oct 8, 2014 at 20:57
  • $\begingroup$ @YuvalFilmus Could you please elaborate on your answer about how the fact that the optimal solution is an integer implies that the approximation is optimal? If I have an approximation algorithm with ratio better than $1/2$ (I mean $\leq 1/2$) and this algorithm returns a result larger than 1 why would this imply that the result has to be 2? The approx. alg could return 1.25, since the appxoimation is better than $1/2$ shouldnt this mean that the optimal solution is 1? $\endgroup$
    – PlsWork
    Sep 15, 2017 at 22:20
  • $\begingroup$ It depends whether it's a maximization or a minimization problem. $\endgroup$ Sep 16, 2017 at 4:42
  • $\begingroup$ I guess it is worth pointing out that we need the objective function to take discrete values for this to work. It seems to me that if the objective function is continuous, then a strongly NP-complete problem may admit an FPTAS without contradiction. (The point being that we will never find an $\epsilon$ small enough to be able to "step down" to the optimal solution.) Although I don't know any examples of such a problem. $\endgroup$
    – kanso37
    Aug 13, 2020 at 0:11
1
$\begingroup$

Strongly NP-Hard problems are problems for whom it had been proved that obtaining an approximation for these problems will allow us solve other NP-Complete problems.

Here's a well-known example:

Assume an algorithm $A$ yields an approximation $\rho$ to the TSP in polynomial time.

Let $G$ be some graph for whom we want to determine if an Hamiltonian Circle exists (a known NP-Complete problem).

Let $G'$ be a complete graph with the same vertices as in $G$ ($V(G) = V(G')$). Connect each two vertices in $G'$ with an edge $e=(u,v)$ with weight 0 if $e$ belong to $E(G)$, otherwise $e$ has a weight of $\rho+1$.

Now find an approximation to the TSP on $G'$ by using $A$, if $A$ produced a solution that is $< \rho+1$, we can determine that there's an Hamiltonian Path in $G$, otherwise, there isn't.

We proved that any approximation algorithm for the TSP will allow us to solve the Hamiltionian Circle problem and thus it is strongly NP-Hard.

$\endgroup$
3
  • $\begingroup$ What if $\rho$ isn't constant? You have to be slightly more careful. $\endgroup$ Oct 24, 2013 at 7:12
  • $\begingroup$ @YuvalFilmus it still holds, let's say $\rho$ depends on the problem size $n$ ($\rho=n^2$ for example), you can still use this procedure to solve the HC-P. $\endgroup$
    – Ron Teller
    Oct 24, 2013 at 7:18
  • $\begingroup$ Ron Teller, what you are saying its the wrong answer to the question, what you notice in TSP is called approximation resistance property, and that's does NOT prove that strongly NP-Complete problems does not have a FPTAS $\endgroup$ Nov 8, 2017 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.