Content deleted Content added
Erel Segal (talk | contribs) No edit summary |
Erel Segal (talk | contribs) |
||
Line 36:
'''Epstein and Sgall'''<ref>{{Cite journal|last=Epstein|first=Leah|last2=Sgall|first2=Jiri|date=2004-05-01|title=Approximation Schemes for Schedulingon Uniformly Related and Identical Parallel Machines|url=https://doi.org/10.1007/s00453-003-1077-7|journal=Algorithmica|language=en|volume=39|issue=1|pages=43–57|doi=10.1007/s00453-003-1077-7|issn=1432-0541}}</ref> generalized the PTAS for uniform machines to handle more general objective functions. Let ''C<sub>i</sub>'' (for ''i'' between 1 and ''m'') be the makespan of machine ''i'' in a given schedule. Instead of minimizing the objective function max(''C<sub>i</sub>''), one can minimize the objective function max(''f''(''C<sub>i</sub>'')), where ''f'' is any fixed function. Similarly, one can minimize the objective function sum(''f''(''C<sub>i</sub>'')).
=== Monotonicity ===
'''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 algorithm that is also ''monotone'' in the machine speed. This is an important consideration for [[strategyproofness]], in settings where the machine speed is the machine's private information, and we want to incentivize machines to reveal their true speed.▼
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''. 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.
▲'''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
== Extensions ==
| |||