1. Greedy is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs
- Author
-
Liu, Fu-Hong, Liu, Hsiang-Hsuan, Wong, Prudence W.H., Sub Algorithms and Complexity, Algorithms and Complexity, Sub Algorithms and Complexity, and Algorithms and Complexity
- Subjects
Schedule ,Mathematical optimization ,021103 operations research ,Competitive analysis ,Matching (graph theory) ,Optimal online algorithm ,Computer science ,Restricted assignment ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,Upper and lower bounds ,01 natural sciences ,Theoretical Computer Science ,Scheduling (computing) ,Smart grid ,Computational Theory and Mathematics ,Bounding overwatch ,010201 computation theory & mathematics ,Theory of computation ,Online algorithm ,Greedy algorithm ,Assignment problem ,Smart grid scheduling - Abstract
We study online scheduling of unit-sized jobs in two related problems, namely, restricted assignment problem and smart grid problem. The input to the two problems are in close analogy but the objective functions are different. We show that the greedy algorithm is an optimal online algorithm for both problems. Typically, an online algorithm is proved to be an optimal online algorithm through bounding its competitive ratio and showing a lower bound with matching competitive ratio. However, our analysis does not take this approach. Instead, we prove the optimality without giving the exact bounds on competitive ratio. Roughly speaking, given any online algorithm and a job instance, we show the existence of another job instance for greedy such that (i) the two instances admit the same optimal offline schedule; (ii) the cost of the online algorithm is at least that of the greedy algorithm on the respective job instance. With these properties, we can show that the competitive ratio of the greedy algorithm is the smallest possible.
- Published
- 2021