Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 08:26, 14 January 2022

Revision as of 08:27, 14 January 2022

Line 135:

* If the approximate oracle returns a solution with value larger than 1, then <math>\mathbf{y}_t</math> is definitely infeasible, and the solution correspond to a configuration that violates a constraint '''a'''. We do a "feasibility cut" in '''<math>\mathbf{y}_t</math>''', cutting the ellipsoid all points '''y''' for which <math>\mathbf{a}\cdot \mathbf{y} > 1</math>.

* If the approximate oracle returns a solution with value at most 1, then '''<math>\mathbf{y}_t</math>''' may or may not be feasible, but '''<math>\mathbf{y}_t</math>''' rounded down (denote it by '''<math>\mathbf{z}_t</math>''') is feasible. By definition of the rounding, we know that <math>\mathbf{n}\cdot \mathbf{z}_t \geq \mathbf{n}\cdot \mathbf{y}_t - \mathbf{n}\cdot \mathbf{1}\cdot (\delta/n) = \mathbf{n}\cdot \mathbf{y}_t - \delta</math>. We still do an "optimality cut" in '''<math>\mathbf{y}_t</math>''': we cut from the ellipsoid all points '''y''' for which <math>\mathbf{n}\cdot \mathbf{y} < \mathbf{n}\cdot \mathbf{y}_t</math>. For the removed points, <math>\mathbf{n}\cdot \mathbf{y} < \mathbf{n}\cdot \mathbf{z}_t+\delta</math>. Therefore, the remaining points are within at most <math>\delta</math> of the optimal solution.

Using the approximate separation oracle gives an approximate solution to the dual. In particular, for any tolerance ''t'', we can find a feasible solution '''y*''' to the dual LP, with <math>\mathbf{n}\cdot \mathbf{y^*} \geq LOPT-t\delta</math>, after at most ''<math>M</math>'' iterations, where <math>M = 4m^2 \ln(mn/gtg\delta)</math>.

As a byproduct of this process, we can consider only the constraints that are activated during the run of the ellipsoid method; there are at most ''<math>M</math> ''such constraints. We add to these, the trivial constraints <math>0 \leq y_j \leq 1</math>. All the other constraints have no effect on the computation of the solution '''y*'''. We can eliminate even more constraints by running this procedure iteratively: we choose a set of constraints, remove them, and find an approximate solution of the dual without these constraints. If the new solution is within the tolerance ''t'' of the old solution, then the constraints are dropped; otherwise, they are retained and a new set of constraints is tried. It can be shown that, after sufficiently many attempts, we will get a dual LP with only ''m'' constraints, which has the same (approximate) solution as the original dual LP. The run-time is <math>O\left(m^8 \log{m} \log^2(\frac{m n}{g h}) + \frac{m^4 n \log{m}}{h}\log(\frac{m n}{g h}) \right)</math>. If the constraints to remove are chosen at random, then the run-time becomes <math>O\left(m^7 \log{m} \log^2(\frac{m n}{g h}) + \frac{m^4 n \log{m}}{h}\log(\frac{m n}{g h}) \right)</math>.