Abstract

Priority Algorithms is a model of computation that generalizes online 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 open question [4]. 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 study normal forms and properties of optimal priority algorithms.

Table of Contents

1 Definitions and Related work 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Job and Interval Scheduling . . . . . . . . . . . . . . . . . . .  2
1.3 Priority Algorithms for Job Scheduling . . . . . . . . . . . . . . 3
1.4 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Definitions and Preliminaries from Complexity Theory . . . . . . . 12
1.6.1 Class characterizations by Turing Machines . . . . . . . . . . . 12
1.6.2 Circuit complexity classes and preliminary results . . . . . . . 13

2 Separating Classes of Priority Algorithms 16
2.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . .16
2.2 Relations between classes of priority algorithms . . . . . . . . . 19
2.2.1 Partially dominated classes of priority algorithms  Main lemmata 19
2.2.2 Almost robust hierarchies according to memory, greediness and
adaptiveness criteria for the Job Scheduling Problem . . . . . . . . . 26
2.2.3 Tables comparing classes of priority algorithms . . . . . . . .  29
2.3 Memory and Priority Algorithms . . . . . . . . . . . . . . . . . . 32
2.3.1 Variations of the memoryless restriction . . . . . . . . . . . . 32
2.3.2 Robust memory hierarchies . . . . . . . . . . . . . . . . . . .  35

3 The complexity of deciding optimality 41
3.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . .  43
3.2 Characterizations of optimal Priority Algorithms for Interval
Scheduling . 45
3.3 Characterization of optimal sets of intervals . . . . . . . . . .  48
3.3.1 The distinct profits case . . . . . . . . . . . . . . . . . . .  48
3.3.2 The general case . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4 Languages in uniform NC 2 . . . . . . . . . . . . . . . . . . . .  58
3.5 Languages in L . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.6 Priority Algorithms for intervals of equal profits . . . . . . . . 62
3.7 PolyIntervalScheduling(m = 1) is complete for NL . . . . . . . . . 64
3.8 Optimal sets of jobs . . . . . . . . . . . . . . . . . . . . . . . 65
3.9 Open problems - Conjectures . . . . . . . . . . . . . . . . . . .  71