Configuration linear program: Difference between revisions

Revision as of 20:30, 25 November 2021

Revision as of 20:50, 25 November 2021

Line 29:

Finally, consider the general case in which there are also some small items, of size less than ''eB''. These items can be added greedily into the bins with the large items using e.g. [[Next-fit bin packing]]. If no new bins are created, then the number of bins is still at most (1+''e'')OPT. If new bins are created, this means that all bins (except maybe the last one) are full up to at least (1-''e'')''B''. Therefore, the number of bins is at most OPT/(1-''e'')+1, which is (1+O(''e''))OPT+1.

=== FractionalThe binfractional packingLP ===

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'':<ref name=":12" /> suppose there are 31 items of size 3 and 7 items of size 4, and the itembin-size sizesis 10. The configurations are: 34,3 44,3 34,3 334, 3,4 33,4 333. The constraints are [0,40,41,42,1,2,3]*'''x'''=31 and [1,2,1,1,0,0,0]*'''x'B''=127. ThenAn theoptimal possiblesolution configurationsto are:the 3333;fractional 333;LP 33,is 334; 3[0, 340, 344; 40, 447,0,0,17/3] 444.That Ifis: wethere hadare only7 three itemsbins of sizeconfiguration 3,334 thenand we17/3 couldbins not use the 3333of configuration 333.

=== Improvements ===