Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 40:
* '''Auletta, De Prisco, Penna and Persiano'''<ref>{{Cite journal|last=Auletta|first=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|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|last=Ambrosio|first=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|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|last=Andelman|first=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|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 journal|last=Kovács|first=Annamária|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|url=https://link.springer.com/chapter/10.1007/11561071_55|journal=Algorithms – ESA 2005|series=Lecture Notes in Computer Science|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.
| |||