Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 21:
* Exact algorithms for minimizing the ''maximum'' completion time on both uniform and unrelated machines, and for minimizing the ''weighted-average completion time'' on ''uniform'' machines. These algorithms run in exponential time (recall that these problems are all NP-hard).
* An approximate algorithm for minimizing the ''maximum'' completion time on ''two uniform'' machines. For any ''ε''>0, their algorithm attains a maximum completion time at most (1+ε)OPT 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]].
'''Hochbaum and Shmoys''',<ref>{{Cite journal|last=Hochbaum|first=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}}</ref> who developed a PTAS for identical processors, extended their PTAS to handle processors with different speeds.
| |||