Content deleted Content added
No edit summary |
m Open access bot: url-access updated in citation with #oabot. |
||
Line 35:
* [[Polynomial-time approximation scheme]]s, which for any ''ε''>0, attain at most (1+ε)OPT. For minimizing the ''maximum'' completion time on two ''uniform'' machines, their algorithm runs in time <math>O(10^{2l} n)</math>, where <math>l</math> is the smallest integer for which <math>\epsilon \geq 2\cdot 10^{-l}</math>. Therefore, the run-time is in <math>O( n / \epsilon^2)</math>, so it is an [[FPTAS]]. For minimizing the ''maximum'' completion time on two ''unrelated'' machines, the run-time is <math>O(10^{l} n^2)</math> = <math>O( n^2 / \epsilon)</math>. They claim that their algorithms can be easily extended for any number of uniform machines, but do not analyze the run-time in this case.
'''Hochbaum and Shmoys'''<ref name=":02">{{Cite journal|last1=Hochbaum|first1=Dorit S.|last2=Shmoys|first2=David B.|date=1987-01-01|title=Using dual approximation algorithms for scheduling problems theoretical and practical results|journal=Journal of the ACM|volume=34|issue=1|pages=144–162|doi=10.1145/7531.7535|issn=0004-5411|s2cid=9739129|doi-access=free}}</ref> presented several approximation algorithms for any number of [[Identical-machines scheduling|''identical'' machines]]. Later,<ref>{{Cite journal|last1=Hochbaum|first1=Dorit S.|last2=Shmoys|first2=David B.|date=1988-06-01|title=A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach|url=https://epubs.siam.org/doi/abs/10.1137/0217033|journal=SIAM Journal on Computing|volume=17|issue=3|pages=539–551|doi=10.1137/0217033|issn=0097-5397|url-access=subscription}}</ref> they developed a PTAS for ''uniform'' machines.
'''Epstein and Sgall'''<ref>{{Cite journal|last1=Epstein|first1=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|s2cid=12965369 |issn=1432-0541|url-access=subscription}}</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 ===
| |||