License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.22
URN: urn:nbn:de:0030-drops-94269
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9426/
Reddy, Goonwanth ;
Vaze, Rahul
Robust Online Speed Scaling With Deadline Uncertainty
Abstract
A speed scaling problem is considered, where time is divided into slots, and jobs with payoff v arrive at the beginning of the slot with associated deadlines d. Each job takes one slot to be processed, and multiple jobs can be processed by the server in each slot with energy cost g(k) for processing k jobs in one slot. The payoff is accrued by the algorithm only if the job is processed by its deadline. We consider a robust version of this speed scaling problem, where a job on its arrival reveals its payoff v, however, the deadline is hidden to the online algorithm, which could potentially be chosen adversarially and known to the optimal offline algorithm. The objective is to derive a robust (to deadlines) and optimal online algorithm that achieves the best competitive ratio. We propose an algorithm (called min-LCR) and show that it is an optimal online algorithm for any convex energy cost function g(.). We do so without actually evaluating the optimal competitive ratio, and give a general proof that works for any convex g, which is rather novel. For the popular choice of energy cost function g(k) = k^alpha, alpha >= 2, we give concrete bounds on the competitive ratio of the algorithm, which ranges between 2.618 and 3 depending on the value of alpha. The best known online algorithm for the same problem, but where deadlines are revealed to the online algorithm has competitive ratio of 2 and a lower bound of sqrt{2}. Thus, importantly, lack of deadline knowledge does not make the problem degenerate, and the effect of deadline information on the optimal competitive ratio is limited.
BibTeX - Entry
@InProceedings{reddy_et_al:LIPIcs:2018:9426,
author = {Goonwanth Reddy and Rahul Vaze},
title = {{Robust Online Speed Scaling With Deadline Uncertainty}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {22:1--22:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-085-9},
ISSN = {1868-8969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9426},
URN = {urn:nbn:de:0030-drops-94269},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.22},
annote = {Keywords: Online Algorithms, Speed Scaling, Greedy Algorithms, Scheduling}
}
|
Keywords: |
|
Online Algorithms, Speed Scaling, Greedy Algorithms, Scheduling |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
13.08.2018 |
