Uniform-machines scheduling: Difference between revisions

Revision as of 19:38, 13 May 2023

Revision as of 01:02, 23 July 2023

Line 39:

=== Monotonicity and Truthfulness ===

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 journalbook|last1=Archer|first1=A.|last2=Tardos|first2=E.|datetitle=2001-10-01Proceedings 42nd IEEE Symposium on Foundations of Computer Science |titlechapter=Truthful mechanisms for one-parameter agents |date=2001-10-01|chapter-url=https://ieeexplore.ieee.org/abstract/document/959924/|journal=Proceedings 42nd IEEE Symposium on Foundations of Computer Science|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 journal|last1=Auletta|first1=Vincenzo|last2=De Prisco|first2=Roberto|last3=Penna|first3=Paolo|last4=Persiano|first4=Giuseppe|date=2004|editor-last=Diekert|editor-first=Volker|editor2-last=Habib|editor2-first=Michel|title=Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines|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 journal|last1=Ambrosio|first1=Pasquale|last2=Auletta|first2=Vincenzo|date=2005|editor-last=Persiano|editor-first=Giuseppe|editor2-last=Solis-Oba|editor2-first=Roberto|title=Deterministic Monotone Algorithms for Scheduling on Related Machines|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 journal|last1=Andelman|first1=Nir|last2=Azar|first2=Yossi|last3=Sorani|first3=Motti|date=2005|editor-last=Diekert|editor-first=Volker|editor2-last=Durand|editor2-first=Bruno|title=Truthful Approximation Mechanisms for Scheduling Selfish Related Machines|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 journalbook|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|title=Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines|chapter-url=https://link.springer.com/chapter/10.1007/11561071_55|journal=Algorithms – ESA 2005|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.

== Extensions ==