Configuration linear program: Difference between revisions

Revision as of 19:07, 7 December 2021

Revision as of 07:05, 8 December 2021

Line 79:

If all items are large (of size at least ''eB''), then each bin in OPT contains at most 1/''e'' items (of size at least ''eB''), so OPT must be at least ''en''. Therefore, Bins(''U'') ≤ (1+''e'')OPT.

Karmarkar and Karp<ref name=":12" /> present a more efficient rounding method which they call ''geometric rounding'' (in contrast to the linear rounding of de-la-Vega and Lueker). Based on these innovations, 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>.

=== Solving the integer LP for the rounded instance ===

A simple way to solve the integer LP is by exhaustive search. Since there are at most ''S^1/e'' configurations, and for each configuration there are at most ''n'' possible values, there are at most <math> n^{S^{1/e}}</math> combinations to check. For each combination, we have to check ''S'' constraints, so the run-time is <math>S\cdot n^{S^{1/e}}</math>, which is polynomial in ''n'' when ''S, e'' are constant.<ref name=":2">{{Cite web|last=Claire Mathieu|title=Approximation Algorithms Part I, Week 3: bin packing|url=https://www.coursera.org/learn/approximation-algorithms-part-1/home/week/3|url-status=live|website=Coursera}}</ref>

Based on these innovations, 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: