I have the following two facts about the Bin Packing Problem that seemingly proves that P=NP !
Let FFD denote the First Fit Decreasing approximation algorithm for the BP problem. Then, we have the following facts:
1. No approximation algorithm for BP can have approx. ratio < 3/2 unless P=NP.
2. According to Johnson 1974, the FFD has performance
FFD(I)=(11/9)OPT(I)+4.
Therefore, the FFD algo. has approx ration
FFD(I)/OPT(I)=(11/9)+4/(OPT(I)),
and for any I such that OPT(I)>(72/5) we have FFD(I)/OPT(I)
The catch is that it is NP-hard to distinguish if the optimum solution is 2 or 3 bins, and you only have an improvement for > 14 bins. See http://ac.informatik.uni-freiburg.de/lak_teaching/ws11_12/combopt/notes/bin_packing.pdf
You misinterpret the understanding of the problem "P = NP". When smart people in the 60s of the last century introduced these concepts, they did not mean approximation algorithms, but exact algorithms. If the problem belongs to the class P, this means only one thing: The exact solution is guaranteed to be found in polynomial time O (P (n)), where P (n) is some polynomial of the input length n, for example n ^ 3. It should be understood also that the degree of the polynomial should not be very large. As for Bin Packing (or 1DBPP), here we are talking only about an approximate algorithm with complexity O (n * log (n)) in the worst case. That is, in other words, the approximate solution FFD (D) is guaranteed not to be more (11/9) * OPT (D) + 4, but this fact has nothing to do with the problem P = NP. So, the trick is that you misuse the understanding of the polynomial algorithm. Let me remind once again, the algorithm must be exact and polynomial at the same time, then and only then this algorithm belongs to the class P.
Gennady Fedulov it is a classical result that Bin Packing does not have a polynomial-time approximation algorithm with factor better than 3/2 unless P = NP. More on this topic in Chapter 16 of http://www.designofapproxalgs.com/book.pdf
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs