A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation

We present a polynomial time approximation scheme for the real-time scheduling problem with fixed priorities when resource augmentation is allowed. For a fixed ε > 0, our algorithmcomputes an assignment using atmost (1+ε)·OPT +1 processors in polynomial time, which is feasible if the processors have speed 1+ε. We also show that, unless P = NP, there does not exist an asymptotic FPTAS for this problem.


Published in:
Automata, Languages and Programming (ICALP'08)
Presented at:
Automata, Languages and Programming, 35th International Colloquium (ICALP 2008), Reykjavik, Iceland, July 7-11, 2008
Year:
2008
Publisher:
Springer
Keywords:
Laboratories:




 Record created 2008-08-21, last modified 2018-03-17

n/a:
Download fulltextPDF
External link:
Download fulltextURL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)