Content deleted Content added
Erel Segal (talk | contribs) |
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 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 journal|last=Archer|first=A.|last2=Tardos|first2=E.|date=2001-10-01|title=Truthful mechanisms for one-parameter agents|url=https://ieeexplore.ieee.org/abstract/document/959924/?casa_token=cfGjnQyxD3kAAAAA:zxN-eY-KjIvmmp2jwarxag2Ha2rbmnwAPyddWQ-_aMdz9JXkxjtb17Ivw5yDgx7llGw_gTSgvfk|journal=Proceedings 42nd IEEE Symposium on Foundations of Computer Science|pages=482–491|doi=10.1109/SFCS.2001.959924}}</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.
'''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.
'''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.
| |||