[ main page ] [ back ]

19/2012 : Automated Competitive Analysis of Real-Time Scheduling with Graph Games

RR Number
19/2012
Author(s)
Krishnendu Chatterjee, Alexander Kler, Ulrich Schmid
Abstract
In this paper, we introduce the powerful tool of algorithmic game theory for competitive analysis of real-time scheduling with firm deadlines. We introduce a novel instance of a partial-observation game that is suitable for this purpose, and prove that all involved decision problems are solveable. Apart from deriving a graph game that allows the automated computation of the competitive ratio, along with an NP-completeness proof, our approach also admits polynomial solutions for computing both the worst-case utility for a given on-line algorithm and the worst-case utility ratio w.r.t. a clairvoyant off-line algorithm. A particularly interesting feature of the proposed approach lies in the fact that additional constraints on the adversary and/or the algorithm, including limited maximum or average load, finiteness of periods of overload, etc., are easily added.
Bibtex
@techreport{ chatterjee:2012-19,
  author =       "Krishnendu Chatterjee and Alexander Kößler and Ulrich Schmid",
  title =        "Automated Competitive Analysis of Real-Time Scheduling with Graph Games",
  institution =  "Technische Universit{\"a}t Wien, Institut f{\"u}r Technische Informatik",
  address =      "Treitlstr. 1-3/182-1, 1040 Vienna, Austria",
  type =         "Research Report",
  year =         "2012",
  number =       "19/2012"
}
Download
Get main.pdf - Adobe PDF-format, (170.2148 KB; posted at July 09 2013)

[ main page ] [ back ]