Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 32:
The ''fractional configuration LP'' of bin-packing is the [[linear programming relaxation]] of the above ILP. It replaces the last constraint <math>x_c\in\{0,\ldots,n\}</math> with the constraint <math>x_c \geq 0</math>. In other words, each configuration can be used a fractional number of times.
* ''Example'': suppose there are 31 items of size 3 and 7 items of size 4, and the bin-size is 10. The configurations are: 4, 44, 34, 334, 3, 33, 333. The constraints are [0,0,1,2,1,2,3]*'''x'''=31 and [1,2,1,1,0,0,0]*'''x'''=7. An optimal solution to the fractional LP is [0,0,0,7,0,0,17/3] That is: there are 7 bins of configuration 334 and 17/3 bins of configuration 333. Note that only two different configurations are needed.
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
<math>OPT(I) \leq FOPT(I)+(S+1)/2</math>.</blockquote>The inequality OPT(I) ≤ FOPT(I)+(S+1)/2 is proved constructively as follows.
* Let '''x''' be an optimal [[basic feasible solution]] of the fractional LP. By definition, the value of '''x''' is FOPT(I). Since the fractional LP has ''S'' constraints, '''x''' has at most ''S'' nonzero variables, that is, at most ''S'' different configurations are used. We construct from '''x''' an integral packing consisting of a ''principal part'' and a ''residual part''.
* The principal part contains floor(''x<sub>c</sub>'') bins of each configuration ''c'' for which ''x<sub>c</sub>'' is nonzero.
* For the residual part (denoted by R), we construct two candidate packings:
** A single bin of each configuration ''c'' for which ''x<sub>c</sub>'' is nonzero; all in all ''S'' bins are needed.
** A greedy packing; it can be proved that this packing requires at most 2*AVG(''R'')+1 bins.
* The smallest of these packings requires min(S, 2*AVG(''R'')+1) = AVG(R) + min(S-AVG(R), AVG(R)+1) ≤ AVG(R) + (S+1)/2.
* Adding to this the rounded-down bins of the principal part yields FOPT(I) + (S+1)/2.
* The execution time of this conversion algorithm is O(''n'' log ''n'').
Based on these lemmas, they present an algorithm with run-time polynomial in <math>n</math> and <math>1/\varepsilon</math>. Their algorithm finds a solution with size at most <math>\mathrm{OPT} + \mathcal{O}(\log^2(OPT))</math>.
=== Improvements ===
This technique was later improved by several authors:
▲* 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> presented an algorithm with run-time polynomial in <math>n</math> and <math>1/\varepsilon</math>. Their algorithm finds a solution with size at most <math>\mathrm{OPT} + \mathcal{O}(\log^2(OPT))</math>.
* Rothvoss<ref name=":22">{{Cite journal|last=Rothvoß|first=T.|date=2013-10-01|title=Approximating Bin Packing within O(log OPT * Log Log OPT) Bins|url=https://ieeexplore.ieee.org/document/6686137|journal=2013 IEEE 54th Annual Symposium on Foundations of Computer Science|volume=|pages=20–29|arxiv=1301.4010|doi=10.1109/FOCS.2013.11|isbn=978-0-7695-5135-7|via=|s2cid=15905063}}</ref> presented an algorithm that generates a solution with size at most <math>\mathrm{OPT} + O(\log(\mathrm{OPT})\cdot \log\log(\mathrm{OPT}))</math>.
| |||