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.
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.
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.
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.