5
$\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$

migrated from programmers.stackexchange.com Oct 23 '13 at 14:22

This question came from our site for professionals, academics, and students working within the systems development life cycle.

6
$\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$
  • 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 '14 at 20:27
  • $\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$ – Yuval Filmus Oct 8 '14 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$ – Anna Vopureta Sep 15 '17 at 22:20
  • $\begingroup$ It depends whether it's a maximization or a minimization problem. $\endgroup$ – Yuval Filmus Sep 16 '17 at 4:42
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$
  • $\begingroup$ What if $\rho$ isn't constant? You have to be slightly more careful. $\endgroup$ – Yuval Filmus Oct 24 '13 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 '13 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$ – Elad Yehezkel Nov 8 '17 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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