1 Search Results for "Reddy, Goonwanth"

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.22

Robust Online Speed Scaling With Deadline Uncertainty

Authors: Goonwanth Reddy and Rahul Vaze

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

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.

Cite as

Goonwanth Reddy and Rahul Vaze. Robust Online Speed Scaling With Deadline Uncertainty. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{reddy_et_al:LIPIcs.APPROX-RANDOM.2018.22,
  author =	{Reddy, Goonwanth and Vaze, Rahul},
  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 =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.22},
  URN =		{urn:nbn:de:0030-drops-94269},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.22},
  annote =	{Keywords: Online Algorithms, Speed Scaling, Greedy Algorithms, Scheduling}
}

Refine by Author
1 Reddy, Goonwanth
1 Vaze, Rahul

Refine by Classification
1 Theory of computation → Scheduling algorithms

Refine by Keyword
1 Greedy Algorithms
1 Online Algorithms
1 Scheduling
1 Speed Scaling

Refine by Type
1 document

Refine by Publication Year
1 2018

1 Search Results for "Reddy, Goonwanth"

Robust Online Speed Scaling With Deadline Uncertainty

Abstract

Cite as

Thanks for your feedback!

Could not send message