Karmarkar–Karp bin packing algorithms: Difference between revisions

Revision as of 14:59, 12 January 2022

Revision as of 19:58, 12 January 2022

Line 19:

* ''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|url-status=live|website=Coursera}}</ref> suppose the item sizes are 3,3,3,3,3,4,4,4,4,4, and ''B''=12. Then there are ''C''=10 possible configurations: 3333; 333; 33, 334; 3, 34, 344; 4, 44, 444. The martix '''''A''''' has two rows: [4,3,2,2,1,1,1,0,0,0] for s=3 and [0,0,0,1,0,1,2,1,2,3] for s=4. The vector '''n''' is [5,5] since there are 5 items of each size. A possible optimal solution is '''x'''=[1,0,0,0,0,0,1,0,0,1], corresponding to using three bins with configurations 3333, 344, 444.

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 Thea high-level description of the algorithm is:<ref name=":0" />

* <math>I</math>

# Let <math>I</math> be the original instance.

#Let <math>J</math> be an instance constructed from <math>I</math> by removing small items.

#Let <math>K</math> be an instance constructed from <math>J</math> by grouping items and rounding the size of items in each group to the highest item in the group.

#Construct the configuration linear program for <math>K</math>.

#Let '''x''' be the solution of the fractional LP (the LP without the integrality constraints).

#Round '''x''' to an integral solution for <math>K</math>.

#Construct from this, a solution for <math>J</math>.

#Add the small items to get a solution for <math>I</math>.

== Guarantees ==

Karmarkar and Karp presented four different algorithms. 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 [[configuration linear program]]: <math>T(m,n)\in O(m^8\log{m}\log^2{n} + m^4 n \log{m}\log{n} )</math>. The algorithms attain the following guarantees: