Greedy is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs

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...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2021-08, Vol.65 (6), p.1009-1032
Main Authors: Liu, Fu-Hong, Liu, Hsiang-Hsuan, Wong, Prudence W. H.
Format: Article
Language:English
Subjects:
Algorithms
Competition
Computer aided scheduling
Computer Science
Greedy algorithms
Lower bounds
Operations research
Optimization
Ratios
Schedules
Smart grid
Special Issue on Approximation and Online Algorithms
Theory of Computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-021-10037-w