Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 19:26, 13 January 2022

Revision as of 08:26, 14 January 2022

Line 128:

* If the total value of the optimal knapsack solution is at most 1, then we say that '''y''' is feasible.

* If the total value of the optimal knapsack solution is larger than 1, then we say that '''y''' is infeasible, and the items in the optimal knapsack solution correspond to a configuration that violates a constraint (since <math>\mathbf{a}\cdot \mathbf{y} > 1</math> for the vector '''a''' that corresponds to this configuration).

The knapsack problem can be solved by dynamic programming in pseudo-polynomial time: <math>O(nm\cdot WV)</math>, where ''nm'' is the number of itemsinputs and ''WV'' is the number of different possible weightsvalues. (forTo exampleget a polynomial-time algorithm, ifwe allcan sizessolve arethe knapsack problem integersapproximately, thenusing theinput runtimerounding. isSuppose we want a solution with tolerance <math>O(n\cdot B)delta</math>). ToWe getcan around polynomial-timeeach algorithmof <math>y_1,\ldots,y_m</math> wedown canto usethe annearest FPTASmultiple forof the knapsack problem''<math>\delta</math>''/''n''. For exampleThen, anthe FPTASnumber byof Lawler<ref>{{Citepossible journal|last=Lawler|first=Eugenevalues L.|date=1979-11-01|title=Fastbetween Approximation0 Algorithmsand for1 Knapsackis Problems|url=https://pubsonline.informs.org''n''/doi/abs/10.1287/moor.4.4.339|journal=Mathematics of Operations Research|volume=4|issue=4|pages=339–356|doi=10.1287/moor.4.4.339|issn=0364-765X}}''<math>\delta</refmath>'', findsand athe solution thatrun-time is at least <math>O(1-m n /\epsilondelta)</math>. timesThe solution is at least the optimal one,solution in timeminus ''<math>O(n \log{1/\epsilon} + 1/\epsilon^4)delta</math> operations''/''n''.

=== Ellipsoid method with an approximate separation oracle ===

=== Solving the dual LP ===

The ellipsoid method should be adapted to use an ''approximate'' separation oracle. Given the current ellipsoid center <math>\mathbf{y}_t</math>:

* 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. HoweverBy 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{Clarify|date=Januaryy} 2022< \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</math>, after at most ''<math>M</math>'' iterations, where <math>M = 4m^2 \ln(mn/gt)</math>.