Hierarchies and complexity results for priority algorithms.
Published: 2004
Language: eng
Number of pages: 64
Description: Priority Algorithms is a model of computation that generalizes on-line computation, attempting to formulate the notion of greedy algorithm. We study questions concerning Priority Algorithms for variants of Job Scheduling. In the first part of the thesis we separate the class of adaptive from the class of greedy and adaptive priority algorithms, which was an early stated open question [5]. We also compare the power of restricted classes of priority algorithms defined for the Job Scheduling and we define a memory hierarchy and show that it is robust. The second part studies questions, where given a finite set of jobs, we want to decide whether a given priority algorithm is optimal, or whether there exists, an optimal priority algorithm. For different settings of these questions we derive containment and hardness results for several complexity classes. Finally, We give an NL-completeness result for a variation of Interval Scheduling.
Notes: Adviser:  Charles Rackoff.

Thesis (M.Sc.)--University of Toronto, 2004.

Electronic version licensed for access by U. of T. users.

Source: Masters Abstracts International, Volume: 42-06, page: 2242.

MICR copy on microfiche (1 microfiche).