Uniform-machines scheduling: Difference between revisions

Revision as of 02:15, 13 August 2023

Revision as of 07:55, 5 September 2023

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).

Line 41:

In some settings, the machine speed is the machine's private information, and we want to incentivize machines to reveal their true speed, that is, we want a [[truthful mechanism]]. An important consideration for attaining truthfulness is ''monotonicity''.<ref>{{Cite book|last1=Archer|first1=A.|last2=Tardos|first2=E.|title=Proceedings 42nd IEEE Symposium on Foundations of Computer Science |chapter=Truthful mechanisms for one-parameter agents |date=2001-10-01|chapter-url=https://ieeexplore.ieee.org/document/959924|pages=482–491|doi=10.1109/SFCS.2001.959924|isbn=0-7695-1390-5 |s2cid=11377808 }}</ref> It means that, if a machine reports a higher speed, and all other inputs remain the same, then the total processing time allocated to the machine weakly increases. For this problem:

* '''Auletta, De Prisco, Penna and Persiano'''<ref>{{Cite journalbook|last1=Auletta|first1=Vincenzo|last2=De Prisco|first2=Roberto|last3=Penna|first3=Paolo|last4=Persiano|first4=Giuseppe|title=Stacs 2004 |chapter=Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines |date=2004|editor-last=Diekert|editor-first=Volker|editor2-last=Habib|editor2-first=Michel|title=Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines|chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-24749-4_53|journal=Stacs 2004|series=Lecture Notes in Computer Science|volume=2996 |language=en|___location=Berlin, Heidelberg|publisher=Springer|pages=608–619|doi=10.1007/978-3-540-24749-4_53|isbn=978-3-540-24749-4}}</ref> presented a 4-approximation monotone algorithm, which runs in polytime when the number of machines is fixed.

*'''Ambrosio and Auletta'''<ref>{{Cite journalbook|last1=Ambrosio|first1=Pasquale|last2=Auletta|first2=Vincenzo|title=Approximation and Online Algorithms |chapter=Deterministic Monotone Algorithms for Scheduling on Related Machines |date=2005|editor-last=Persiano|editor-first=Giuseppe|editor2-last=Solis-Oba|editor2-first=Roberto|title=Deterministic Monotone Algorithms for Scheduling on Related Machines|chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-31833-0_22|journal=Approximation and Online Algorithms|series=Lecture Notes in Computer Science|volume=3351 |language=en|___location=Berlin, Heidelberg|publisher=Springer|pages=267–280|doi=10.1007/978-3-540-31833-0_22|isbn=978-3-540-31833-0}}</ref> proved that the [[Longest processing time|Longest Processing Time]] algorithm is monotone whenever the machine speeds are powers of some c ≥ 2, but not when c ≤ 1.78. In contrast, [[List scheduling]] is not monotone for ''c'' > 2.

* '''Andelman, Azar and Sorani'''<ref>{{Cite journalbook|last1=Andelman|first1=Nir|last2=Azar|first2=Yossi|last3=Sorani|first3=Motti|title=Stacs 2005 |chapter=Truthful Approximation Mechanisms for Scheduling Selfish Related Machines |date=2005|editor-last=Diekert|editor-first=Volker|editor2-last=Durand|editor2-first=Bruno|title=Truthful Approximation Mechanisms for Scheduling Selfish Related Machines|chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-31856-9_6|journal=Stacs 2005|series=Lecture Notes in Computer Science|volume=3404 |language=en|___location=Berlin, Heidelberg|publisher=Springer|pages=69–82|doi=10.1007/978-3-540-31856-9_6|isbn=978-3-540-31856-9}}</ref> presented a 5-approximation monotone algorithm, which runs in polytime even when the number of machines is variable.

* '''Kovacz'''<ref>{{Cite book|last=Kovács|first=Annamária|title=Algorithms – ESA 2005 |chapter=Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines |date=2005|editor-last=Brodal|editor-first=Gerth Stølting|editor2-last=Leonardi|editor2-first=Stefano |chapter-url=https://link.springer.com/chapter/10.1007/11561071_55 |series=Lecture Notes in Computer Science|volume=3669 |language=en|___location=Berlin, Heidelberg|publisher=Springer|pages=616–627|doi=10.1007/11561071_55|isbn=978-3-540-31951-1}}</ref> presented a 3-approximation monotone algorithm.