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



Liu, Fu-Hong ORCID: 0000-0001-6073-8179, Liu, Hsiang-Hsuan and Wong, Prudence WH ORCID: 0000-0001-7935-7245
(2021) Greedy is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs. Theory of Computing Systems, 65 (6). pp. 1009-1032.

[img] Text
TOCS.pdf - Author Accepted Manuscript

Download (379kB) | Preview

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.

Item Type: Article
Additional Information: Theory of Computing Systems, based on WAOA 2019 paper, GS is 2 at the moment.
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 12 Apr 2021 09:44
Last Modified: 18 Jan 2023 22:53
DOI: 10.1007/s00224-021-10037-w
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3119043