Content deleted Content added
Alter: title, template type. Add: title, chapter-url, chapter. Removed or converted URL. Removed parameters. Some additions/deletions were parameter name changes. | Use this tool. Report bugs. | #UCB_Gadget |
m Open access bot: doi added to citation with #oabot. |
||
Line 29:
A constant-factor approximation is attained by the [[Longest-processing-time-first scheduling#uniform|Longest-processing-time-first algorithm]] (LPT).
'''Horowitz and Sahni<ref name=":0">{{Cite journal|last1=Horowitz|first1=Ellis|last2=Sahni|first2=Sartaj|date=1976-04-01|title=Exact and Approximate Algorithms for Scheduling Nonidentical Processors|url=https://doi.org/10.1145/321941.321951|journal=Journal of the ACM|volume=23|issue=2|pages=317–327|doi=10.1145/321941.321951|s2cid=18693114 |issn=0004-5411|doi-access=free}}</ref>''' presented:
* Exact [[dynamic programming]] algorithms for minimizing the ''maximum'' completion time on both uniform and unrelated machines. These algorithms run in exponential time (recall that these problems are all NP-hard).
| |||