Header menu link for other important links
X
Robust online speed scaling with deadline uncertaint
Goonwanth Ramachandra C. Reddy
Published in Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
2018
Volume: 116
   
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(κ) = κα, α≥2, we give concrete bounds on the competitive ratio of the algorithm, which ranges between 2.618 and 3 depending on the value of. 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 p2. 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. © 2018 Aditya Bhaskara and Srivatsan Kumar.
About the journal
JournalLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISSN18688969
Open AccessNo
Concepts (14)
  •  related image
    Combinatorial optimization
  •  related image
    Cost functions
  •  related image
    Random processes
  •  related image
    Scheduling
  •  related image
    Scheduling algorithms
  •  related image
    Competitive ratio
  •  related image
    Energy cost
  •  related image
    Greedy algorithms
  •  related image
    Lower bounds
  •  related image
    Off-line algorithm
  •  related image
    On-line algorithms
  •  related image
    OPTIMAL COMPETITIVE RATIOS
  •  related image
    SPEED SCALING
  •  related image
    Approximation algorithms