Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657000 | Journal of Algorithms | 2005 | 35 Pages |
Abstract
We give an algorithm to minimize the total completion time on-line on a single machine, using restarts, with a competitive ratio of 3/2. The optimal competitive ratio without using restarts is 2 for deterministic algorithms and e/(eâ1)â1.582 for randomized algorithms. This is the first restarting algorithm to minimize the total completion time that is proved to be better than an algorithm that does not restart.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Rob van Stee, Han La Poutré,