Hierarchies for classes of priority algorithms for Job Scheduling

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

Priority algorithm is a model of computation capturing the notion of greedy and greedy-like algorithm. This paper concerns priority algorithms for Job Scheduling. Three main restrictions are defined for priority algorithms, namely: memoryless, greedy and fixed. It was asked in [A. Borodin, M.N. Nielsen, C. Rackoff, (Incremental) priority algorithms, in: Proc. 13th Annu. Symp. Discrete Algorithms (SODA), January 2002, pp. 752-761 (also in Algorithmica 37(4) (2003) 295-326] whether the general class of priority algorithms is of different power from the restricted class of greedy-priority algorithms (for the Job Scheduling problem). We answer this question affirmatively by showing that a specific priority algorithm cannot be simulated by any greedy-priority algorithm on every input. Furthermore we systematically compare every two classes of priority algorithms for different settings of Job Scheduling. We also define a hierarchy for priority algorithms of bounded memory which lies between the class of memoryless and the class of priority algorithms with memory, and we show that this memory hierarchy is robust.

Original languageEnglish (US)
Pages (from-to)181-189
Number of pages9
JournalTheoretical Computer Science
Volume352
Issue number1-3
DOIs
StatePublished - Mar 7 2006
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • Algorithmic paradigms
  • Classes
  • Greedy algorithm

Fingerprint

Dive into the research topics of 'Hierarchies for classes of priority algorithms for Job Scheduling'. Together they form a unique fingerprint.

Cite this