Configuration linear program: Difference between revisions

Revision as of 21:20, 17 December 2021

Revision as of 20:19, 8 January 2022

Line 29:

In short, the fractional LP can be written as follows:<blockquote><math>\text{minimize}~~\mathbf{1}\cdot \mathbf{x}~~~\text{s.t.}~~ A \mathbf{x}\geq \mathbf{n}~~~\text{and}~~ \mathbf{x}\geq 0</math></blockquote>Where '''1''' is the vector (1,...,1) of size ''C'', '''A''' is an ''S''-by-''C'' matrix in which each column represents a single configuration, and '''n''' is the vector (''s''₁,...,''s_S'').

Let FOPT(I) be the optimal solution of the fractional LP for instance I, and OPT(I) the optimal solution of the integral LP. Let AVGTOPT be the sum of all sizes divided by ''B''; this is the theoretically-optimal number of bins, when all bins are completely filled with items or item-fractions. The following relations are obvious:

* AVGTOPT(I) ≤ FOPT(I), since AVGTOPT(I) is the (possibly fractional) number of bins when all bins are completely filled with items or fractions of items. Clearly, no solution can be more efficient.

* FOPT(I) ≤ OPT(I), since FOPT(I) is a solution to a minimization problem with fewer constraints.

* OPT(I) < 2*AVGTOPT(I), since in any packing with at least 2*AVGTOPT(I) bins, the sum of the two least-full bins is at most ''B'', so they can be combined into a single bin.

=== Rounding the fractional LP ===

Line 41:

* For the residual part (denoted by ''R''), we construct two candidate packings:

** A single bin of each configuration ''c'' for which ''x_c'' > 0; all in all ''S'' bins are needed.

** A greedy packing, with fewer than 2*AVGTOPT(''R'') bins (since if there are at least 2*AVGTOPT(''R'') bins, the two smallest ones can be combined).

* The smallest of these packings requires min(S, 2*AVGTOPT(''R'')) ≤ average(S, 2*AVGTOPT(''R'')) = AVGTOPT(R) + S/2.

* Adding to this the rounded-down bins of the principal part yields FOPT(I) + S/2.

* The execution time of this conversion algorithm is O(''n'' log ''n'').