Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 49:
* For any ''r'' >0, an algorithm with approximation ratio at most (7/6+2<sup>−''r''</sup> ) in time <math>O(n(r m^4+\log{n}))</math>.
* For any ''ε''>0, an algorithm with approximation ratio at most (1+ε) in time <math>O((n/\varepsilon)^{(1/\varepsilon^2)})</math> . This is a [[Polynomial-time approximation scheme|PTAS]]. Note that, when the number of machines is a part of the input, the problem is [[Strong NP-completeness|strongly NP-hard]], so no FPTAS is possible.
**The run-time of this algorithm was later improved to <math>O\left((n/\varepsilon)^{(1/\varepsilon)\log{(1/\varepsilon)}}\right)</math>.<ref>{{Cite journal|date=1989-05-08|title=Bin packing with restricted piece sizes|url=https://www.sciencedirect.com/science/article/abs/pii/0020019089902238|journal=Information Processing Letters|language=en|volume=31|issue=3|pages=145–149|doi=10.1016/0020-0190(89)90223-8|issn=0020-0190}}</ref>
Later,<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> they developed a PTAS for ''uniform'' machines.
| |||