Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) |
||
Line 41:
Let FOPT(I) be the optimal solution of the fractional LP for instance I, and OPT(I) the optimal solution of the integral LP. Let AVG be the sum of all sizes divided by ''B'' (this would be the number of bins if we could cut items).
It is obvious that AVG(I) ≤ FOPT(I) ≤ OPT(I): AVG(I) is the number of bins when all bins are completely full - no solution can be better than this. FOPT(I) is the solution to the LP, which is less constrained than the ILP, so it is at least as good as OPT(I). Karmarkar and Karp<ref name=":12">{{cite journal|last1=Karmarkar|first1=Narendra|last2=Karp|first2=Richard M.|date=November 1982|title=An efficient approximation scheme for the one-dimensional bin-packing problem|url=https://ieeexplore.ieee.org/document/4568405/references#references|journal=23rd Annual Symposium on Foundations of Computer Science (SFCS 1982)|pages=312–320|doi=10.1109/SFCS.1982.61|s2cid=18583908}}</ref> prove the following inequalities for any instance I: ▼
▲It is obvious that AVG(I) ≤ FOPT(I) ≤ OPT(I): AVG(I) is the number of bins when all bins are completely full - no solution can be better than this. FOPT(I) is the solution to the LP, which is less constrained than the ILP, so it is at least as good as OPT(I). Karmarkar and Karp<ref name=":12">{{cite journal|last1=Karmarkar|first1=Narendra|last2=Karp|first2=Richard M.|date=November 1982|title=An efficient approximation scheme for the one-dimensional bin-packing problem|url=https://ieeexplore.ieee.org/document/4568405/references#references|journal=23rd Annual Symposium on Foundations of Computer Science (SFCS 1982)|pages=312–320|doi=10.1109/SFCS.1982.61|s2cid=18583908}}</ref> prove the following inequalities for any instance I:
* <math>OPT(I) \leq 2\cdot AVG(I) + 1</math>.
* <math>OPT(I) \leq FOPT(I)+(S+1)/2</math>.
| |||