Content deleted Content added
m v2.04b - Bot T18 CW#553 - Fix errors for CW project (<nowiki> tags - Link equal to linktext) |
Erel Segal (talk | contribs) No edit summary |
||
Line 35:
'''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>'')).
'''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.
== Extensions ==
| |||