Multifit algorithm: Difference between revisions
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
| Line 14: | Line 14: | ||
* 15 / 13 ≈ 1.15 for ''k'' = 3; |
* 15 / 13 ≈ 1.15 for ''k'' = 3; |
||
* 20 / 17 ≈ 1.176 for ''k'' = 4,5,6,7. |
* 20 / 17 ≈ 1.176 for ''k'' = 4,5,6,7. |
||
For general ''k'', it was proved that the upper bound is 1.220.<ref name=":0" /> It was later improved to 6/5=1.2,<ref name=":1">{{Cite journal|last=Friesen|first=Donald K.|date=1984-02-01|title=Tighter Bounds for the Multifit Processor Scheduling Algorithm|url=https://epubs.siam.org/doi/abs/10.1137/0213013|journal=SIAM Journal on Computing|volume=13|issue=1|pages=170–181|doi=10.1137/0213013|issn=0097-5397}}</ref> and later to 13/11≈1.182.<ref>{{Cite journal|last=Yue|first=Minyi|date=1990-12-01|title=On the exact upper bound for the multifit processor scheduling algorithm|url=https://doi.org/10.1007/BF02216826|journal=Annals of Operations Research|language=en|volume=24|issue=1|pages=233–259|doi=10.1007/BF02216826|issn=1572-9338}}</ref> |
For general ''k'', it was proved that the upper bound is 1.220.<ref name=":0" /> It was later improved to 6/5=1.2,<ref name=":1">{{Cite journal|last=Friesen|first=Donald K.|date=1984-02-01|title=Tighter Bounds for the Multifit Processor Scheduling Algorithm|url=https://epubs.siam.org/doi/abs/10.1137/0213013|journal=SIAM Journal on Computing|volume=13|issue=1|pages=170–181|doi=10.1137/0213013|issn=0097-5397}}</ref> and later to 13/11≈1.182.<ref name=":2">{{Cite journal|last=Yue|first=Minyi|date=1990-12-01|title=On the exact upper bound for the multifit processor scheduling algorithm|url=https://doi.org/10.1007/BF02216826|journal=Annals of Operations Research|language=en|volume=24|issue=1|pages=233–259|doi=10.1007/BF02216826|issn=1572-9338}}</ref> The original proof of this missed some cases; a complete and simple proof is presented in <ref>{{Citation|last=Cao|first=Feng|title=Determining the Performance Ratio of Algorithm Multifit for Scheduling|date=1995|url=https://doi.org/10.1007/978-1-4613-3557-3_5|work=Minimax and Applications|pages=79–96|editor-last=Du|editor-first=Ding-Zhu|series=Nonconvex Optimization and Its Applications|place=Boston, MA|publisher=Springer US|language=en|doi=10.1007/978-1-4613-3557-3_5|isbn=978-1-4613-3557-3|access-date=2021-08-23|editor2-last=Pardalos|editor2-first=Panos M.}}</ref>. The 13/11 cannot be improved: there is an instance with ''k''=13 in which the approximation ratio is exactly 13/11.<ref name=":2" /> |
||
== References == |
== References == |
||
Revision as of 12:13, 23 August 2021
The multifit algorithm is an algorithm for multiway number partitioning, originally developed for the problem of identical-machines scheduling. It was developed by Coffman, Garey and Johnson.[1] Its novelty comes from the fact that it uses an algorithm for another famous problem - the bin packing problem - as a subroutine.
The algorithm
The input to the algorithm is a set S of numbers, and a parameter k. The required output is a partition of S into k subsets, such that the largest subset sum (also called the makespan) in as small as possible.
The algorithm uses as a subroutine, an algorithm called first-fit-decreasing bin packing (FFD). The FFD algorithm takes as input the same set S of numbers, and a bin-capacity c. It heuristically packs numbers into bins such that the sum of numbers in each bin is at most c, aiming to use as few bins as possible. While FFD is not optimal, it always finds a packing with at most bins, where OPT is the optimal number.
Naturally, when c is smaller, the number of bins required by FFD is larger. The Multifit algorithm performs a binary search to find the smallest c for which FFD uses k bins.
Analysis
Multifit is a constant-factor approximation algorithm. It always finds a partition in which the makespan is at most a constant factor larger than the optimal makespan. The constant factor for small values of k is:[1]
- 8 / 7 ≈ 1.14 for k = 2;
- 15 / 13 ≈ 1.15 for k = 3;
- 20 / 17 ≈ 1.176 for k = 4,5,6,7.
For general k, it was proved that the upper bound is 1.220.[1] It was later improved to 6/5=1.2,[2] and later to 13/11≈1.182.[3] The original proof of this missed some cases; a complete and simple proof is presented in [4]. The 13/11 cannot be improved: there is an instance with k=13 in which the approximation ratio is exactly 13/11.[3]
References
- ^ a b c Coffman, Jr., E. G.; Garey, M. R.; Johnson, D. S. (1978-02-01). "An Application of Bin-Packing to Multiprocessor Scheduling". SIAM Journal on Computing. 7 (1): 1–17. doi:10.1137/0207001. ISSN 0097-5397.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - ^ Friesen, Donald K. (1984-02-01). "Tighter Bounds for the Multifit Processor Scheduling Algorithm". SIAM Journal on Computing. 13 (1): 170–181. doi:10.1137/0213013. ISSN 0097-5397.
- ^ a b Yue, Minyi (1990-12-01). "On the exact upper bound for the multifit processor scheduling algorithm". Annals of Operations Research. 24 (1): 233–259. doi:10.1007/BF02216826. ISSN 1572-9338.
- ^ Cao, Feng (1995), Du, Ding-Zhu; Pardalos, Panos M. (eds.), "Determining the Performance Ratio of Algorithm Multifit for Scheduling", Minimax and Applications, Nonconvex Optimization and Its Applications, Boston, MA: Springer US, pp. 79–96, doi:10.1007/978-1-4613-3557-3_5, ISBN 978-1-4613-3557-3, retrieved 2021-08-23