Abstract
We continue the recent study of priority algorithms initiated by Borodin et al. [Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, 2002, pp. 752-761]. The definition of a priority algorithm nicely captures the idea of a "greedy-like" type algorithm. While priority algorithms are applicable to many optimization problems, in this paper we consider the problem of makespan minimization in scheduling in the subset model. We show that by using a fixed priority algorithm one cannot achieve a considerable improvement over the approximation ratio given by the online greedy algorithm. Namely, we present an Ω(logm/loglogm) lower bound on the approximation ratio of any fixed priority algorithm where m is the number of machines.
Original language | English (US) |
---|---|
Pages (from-to) | 153-157 |
Number of pages | 5 |
Journal | Information Processing Letters |
Volume | 84 |
Issue number | 3 |
DOIs | |
State | Published - Nov 15 2002 |
Keywords
- Approximation algorithms
- Scheduling
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications