Configuration linear program: Difference between revisions

Revision as of 07:09, 26 November 2021

Revision as of 08:34, 26 November 2021

Line 26:

** Write the integer LP for the rounded instance. Since the number of sizes is ''S'' and there are at most 1/''e'' items in each bin, the total number of configurations is at most ''S''^1/''e''.

** Solve the integer LP.

* Allocate the small items greedily, e.g. with [[next-fit bin packing]]. If no new bins are created, then we are done. 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(2''e''))OPT+1.

The algorithms differ in how they round the instance and in how the solve the integer LP.