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



Liu, Fu-Hon, Liu, Hsiang-Hsuan and Wong, PW ORCID: 0000-0001-7935-7245
(2020) Greedy is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs. In: Proceedings of the Workshop on Approximation and Online Algorithms (WAOA 2019).

[img] Text
waoa2019_final.pdf - Author Accepted Manuscript

Download (334kB) | 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: Conference or Workshop Item (Unspecified)
Uncontrolled Keywords: Optimal online algorithm, Restricted assignment, Smart grid scheduling
Depositing User: Symplectic Admin
Date Deposited: 10 Feb 2020 10:42
Last Modified: 19 Jan 2023 00:03
DOI: 10.1007/978-3-030-39479-0_15
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3074340