Content deleted Content added
Rkieferbaum (talk | contribs) m v2.05 - Fix errors for CW project (Link equal to linktext) |
Citation bot (talk | contribs) Removed URL that duplicated identifier. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 456/990 |
||
| (10 intermediate revisions by 6 users not shown) | |||
Line 1:
{{short description|Set of related approximation algorithms for the bin packing problem}}
{{Multiple issues|{{refimprove|date=March 2022}}{{more footnotes|date=March 2022}}}}
The '''
The KK algorithms were considered a breakthrough in the study of bin packing: the previously-known algorithms found multiplicative approximation, where the number of bins was at most <math>r\cdot \mathrm{OPT}+s</math> for some constants <math>r>1, s>0</math>, or at most <math>(1+\varepsilon)\mathrm{OPT} + 1</math>.<ref name=":0">{{cite journal|last1=Fernandez de la Vega|first1=W.|last2=Lueker|first2=G. S.|date=1981|title=Bin packing can be solved within 1 + ε in linear time|journal=Combinatorica|language=en|volume=1|issue=4|pages=349–355|doi=10.1007/BF02579456|issn=1439-6912|s2cid=10519631}}</ref> The KK algorithms were the first ones to attain an additive approximation.
Line 21 ⟶ 22:
The KK algorithms essentially solve the [[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~~~\text{and}~~ \mathbf{x}~\text{is an integer}~</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.
* ''Example'':<ref name=":22">{{Cite web|last=Claire Mathieu|title=Approximation Algorithms Part I, Week 3: bin packing|url=https://www.coursera.org/learn/approximation-algorithms-part-1/home/week/3
There are two main difficulties in solving this problem. First, it is an [[Integer programming|integer linear program]], which is computationally hard to solve. Second, the number of variables is ''C'' - the number of configurations, which may be enormous. The KK algorithms cope with these difficulties using several techniques, some of which were already introduced by de-la-Vega and Lueker.<ref name=":0" /> Here is a high-level description of the algorithm (where <math>I</math> is the original instance):
Line 132 ⟶ 133:
* 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(m\cdot V)</math>, where ''m'' is the number of inputs and ''V'' is the number of different possible values. To get a polynomial-time algorithm, we can solve the knapsack problem approximately, using input rounding. Suppose we want a solution with tolerance <math>\delta</math>. We can round each of <math>y_1,\ldots,y_m</math> down to the nearest multiple of ''<math>\delta</math>''/''n''. Then, the number of possible values between 0 and 1 is ''n''/''<math>\delta</math>'', and the run-time is <math>O(m n /\delta)</math>. The solution is at least the optimal solution minus ''<math>\delta</math>''/''n''.
=== Ellipsoid method with an approximate separation oracle ===
Line 163 ⟶ 164:
O\left(m^8 \ln{m} \ln^2(\frac{m n}{g h}) + \frac{m^4 n \ln{m}}{h}\ln(\frac{m n}{g h}) \right)</math>,
The expected total run-time of the [[randomized algorithm]] is: <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>.
== End-to-end algorithms ==
Karmarkar and Karp presented three algorithms, that use the above techniques with different parameters. The run-time of all these algorithms depends on a function <math>T(\cdot,\cdot)</math>, which is a polynomial function describing the time it takes to solve the fractional LP with tolerance ''h''=1, which is, for the deterministic version,<math>T(m,n)\in O(m^8\log{m}\log^2{n} + m^4 n \log{m}\log{n} )</math>.
Line 215 ⟶ 216:
The KK techniques were improved later, to provide even better approximations.
Rothvoss<ref name=":2">{{Cite
Hoberg and Rothvoss<ref name=":3">{{Citation|last1=Hoberg|first1=Rebecca|title=A Logarithmic Additive Integrality Gap for Bin Packing|date=2017-01-01|work=Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms|pages=2616–2625|series=Proceedings|publisher=Society for Industrial and Applied Mathematics|doi=10.1137/1.9781611974782.172|isbn=978-1-61197-478-2|last2=Rothvoss|first2=Thomas|s2cid=1647463|doi-access=free|arxiv=1503.08796}}</ref> use a similar scheme in which the items are first packed into "containers", and then the containers are packed into bins. Their algorithm needs at most <math>b_J \leq OPT(I) + O(\log(OPT))</math> bins.
== References ==
| |||