Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) →Fractional bin packing: Copy some stuff from configuration linear program |
||
Line 29:
* LOPT(I) ≤ OPT(I), since LOPT(I) is a solution to a minimization problem with fewer constraints.
* OPT(I) < 2*FOPT(I), since in any packing with at least 2*FOPT(I) bins, the sum of the two least-full bins is at most ''B'', so they can be combined into a single bin.
== The dual LP ==
The [[dual linear program]] of the fractional LP is:<blockquote><math>\text{maximize}~~\mathbf{n}\cdot \mathbf{y}~~~\text{s.t.}~~ A^T \mathbf{y} \leq \mathbf{1}~~~\text{and}~~ \mathbf{y}\geq 0</math>.</blockquote>It has ''S'' variables ''y''<sub>1</sub>,...,''y<sub>S</sub>'', and ''C'' constraints - one for each configuration. It has the following economic interpretation.<ref name=":122">{{cite journal|last1=Karmarkar|first1=Narendra|last2=Karp|first2=Richard M.|date=November 1982|title=An efficient approximation scheme for the one-dimensional bin-packing problem|url=https://ieeexplore.ieee.org/document/4568405/references#references|journal=23rd Annual Symposium on Foundations of Computer Science (SFCS 1982)|pages=312–320|doi=10.1109/SFCS.1982.61|s2cid=18583908}}</ref> For each size ''s'', we should determine a nonnegative price ''y<sub>s</sub>''. Our profit is the total price of all items. We want to maximize the profit '''n''' '''y''' subject to the constraints that the total price of items in each configuration is at most 1.
== 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 might be huge. Karmarkar and Karp<ref name=":122" /> present an algorithm that, for any tolerance factor ''h'', finds a basic feasible solution of cost at most LOPT(I) + ''h'', and runs in time:
<math>O\left(S^8 \log{S} \log^2(\frac{S n}{e h}) + \frac{S^4 n \log{S}}{h}\log(\frac{S n}{e h}) \right)</math>,
where ''S'' is the number of different sizes, ''n'' is the number of different items, and the size of the smallest item is ''eB''. In particular, if ''e'' ≥ 1/''n'' and ''h''=1, the algorithm finds a solution with at most LOPT+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}{e h}) + \frac{S^4 n \log{S}}{h}\log(\frac{S n}{e h}) \right)</math>.
Their algorithm uses [[separation oracle]] to the dual LP.
== Rounding the fractional LP ==
Given an optimal solution to the fractional LP, it can be rounded into a solution for the integral ILP, proving that OPT(I) ≤ LOPT(I) + ''m''/2:
* Let '''x''' be an optimal [[basic feasible solution]] of the fractional LP. By definition, the value of '''x''' is LOPT(I). Since the fractional LP has ''S'' constraints, '''x''' has at most ''S'' nonzero variables, that is, at most ''S'' different configurations are used. We construct from '''x''' an integral packing consisting of a ''principal part'' and a ''residual part''.
* The principal part contains floor(''x<sub>c</sub>'') bins of each configuration ''c'' for which ''x<sub>c</sub>'' > 0.
* For the residual part (denoted by ''R''), we construct two candidate packings:
** A single bin of each configuration ''c'' for which ''x<sub>c</sub>'' > 0; all in all ''S'' bins are needed.
** A greedy packing, with fewer than 2*FOPT(''R'') bins (since if there are at least 2*FOPT(''R'') bins, the two smallest ones can be combined).
* The smallest of these packings requires min(S, 2*FOPT(''R'')) ≤ average(S, 2*FOPT(''R'')) = FOPT(R) + S/2.
* Adding to this the rounded-down bins of the principal part yields LOPT(I) + S/2.
* The execution time of this conversion algorithm is O(''n'' log ''n'').
== References ==
| |||