Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) No edit summary |
||
Line 52:
TODO
== 3. Constructing and rounding the LP ==
The main tool used by the KK algorithms is the fractional [[configuration linear program]]:<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>Here, '''''A''''' is a matrix with ''m'' rows. Each column of '''''A''''' represents a feasible ''configuration'' - a multiset of item-sizes, such that the sum of all these sizes is at most ''B''. The set of configurations is ''C''. '''x''' is a vector of size ''C.'' Each element ''x<sub>c</sub>'' of '''x''' represents the number of times configuration ''c'' is used. If '''x''' is integral then the solution to this problem is exactly OPT. Since '''x''' is allowed to be fractional, the solution might be smaller; denote it by LOPT. Moreover, let ''FOPT'' = (''a''<sub>1</sub>+...+''a<sub>n</sub>'')/''B'' = the theoretically-optimal number of bins, when all bins are completely filled with items or item fractions. The following relations are obvious:
Line 60 ⟶ 61:
* 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 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. 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 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:
Line 90 ⟶ 75:
''e'' - a fraction in (0,1), such that ''eB'' is the smallest size of an item.
=== 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. 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 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.
== Guarantees ==
| |||