Name
Abstract | ||
|---|---|---|
We consider the multiprocessor scheduling problem in which one must schedule n independent tasks nonpreemptively on m identical, parallel machines, such that the completion time of the last task is minimal. For this well-studied problem the Largest Differencing Method due to Karmarkar and Karp outperforms other existing polynomial-time approximation algorithms from an average-case perspective. For m ≥ 3, its worst-case performance has remained a challenging open problem. We show that its performance ratio is bounded between 43 − 1(3(m-1)) and 43−13m. We also analyze the performance ratio if in addition to the number of machines, the number of tasks n is fixed as well. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1016/S1571-0653(04)00442-1 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
linear program,multiprocessor scheduling | Approximation algorithm,Open problem,Multiprocessor scheduling,Scheduling (computing),Performance ratio,Computer science,Parallel computing,Linear programming,Bounded function | Journal |
Volume | ISSN | Citations |
13 | 1571-0653 | 3 |
PageRank | References | Authors |
0.45 | 15 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wil Michiels | 1 | 95 | 8.66 |
| Jan Korst | 2 | 175 | 19.94 |
| Emile H. L. Aarts | 3 | 1641 | 307.48 |
| Jan van Leeuwen i | 4 | 3 | 0.45 |