Randomized algorithms for on-line scheduling problems : how low can't you go?
Leen Stougie, Arjen P.A. Vestjens · TU/e Research Portal · 2000
We prove lower bounds on the competitive ratio of randomized algorithms for several on-line scheduling problems. The main result is a bound of e/(e-1) for the on-line problem with objective minimizing the sum of completion times of jobs that arrive over time at their release times and are to be processed on a single machine. This lower bound shows that a randomized algorithm designed in Chekuri et al. (Proceedings of the Eighth ACM-SIAM Symposium on Discrete Algorithms, 1997, 609-618) is a best possible randomized algorithm for this problem.