Content deleted Content added
Erel Segal (talk | contribs) Move stuff to high-multiplicity bin packing |
Erel Segal (talk | contribs) No edit summary |
||
Line 24:
=== The fractional LP ===
The '''fractional configuration LP of bin-packing''' It 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. The relaxation was first presented by Gilmore and Gomory<ref name="Gilmore61" />, and it is often called the '''Gilmore-Gomory linear program'''.<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>
* ''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.
| |||