Configuration linear program: Difference between revisions

Revision as of 09:05, 26 November 2021

Revision as of 09:34, 26 November 2021

Line 50:

=== Solving the fractional LP ===

A linear program with no integrality constraints can be solved in time polynomial in the number of variables and constraints. The problem is that the number of variables in the fractional configuration LP is equal to the number of possible configurations, which ismight exponentialbe in 1/''e''huge. Karmarkar and Karp<ref name=":12" /> present an algorithm that, runs in time polynomial in 1/''e.'' Forfor any tolerance factor ''h'', their algorithm finds a basic feasible solution of cost at most FOPT(I) + ''h'', and runs in time:

<math>O\left(S^8 \log{S} \log^2(\frac{S n}{ae h}) + \frac{S^4 n \log{S}}{h}\log(\frac{S n}{ae h}) \right)</math>,

where ''S'' is the number of different sizes, ''n'' is the number of different items, and ''a'' is the size of the smallest item (divided byis ''BeB''). AIn randomizedparticular, variantif of''e'' this ≥ 1/''n'' and ''h''=1, the algorithm runsfinds ina expectedsolution with at most FOPT+1 bins in time: <math>O\left(S^8 \log{S} \log^2{n} + S^4 n \log{S}\log{n} \right)</math>.

A randomized variant of this algorithm runs in expected time:

<math>O\left(S^7 \log{S} \log^2(\frac{S n}{a h}) + \frac{S^4 n \log{S}}{h}\log(\frac{S n}{a h}) \right)</math>.

<math>O\left(S^7 \log{S} \log^2(\frac{S n}{ae h}) + \frac{S^4 n \log{S}}{h}\log(\frac{S n}{ae h}) \right)</math>.

Their algorithm uses [[separation oracle]] to the dual LP.

=== Approximation algorithms ===

The general scheme of theseapproximation algorithms is:

* Separate the items to "small" (smaller than ''eB'', for some fraction e in (0,1)) and "large" (at least ''eB'').