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

• Presented at: Automata, Languages and Programming, 35th International Colloquium (ICALP 2008), Reykjavik, Iceland, July 7-11, 2008
• Published in: Automata, Languages and Programming (ICALP'08)
• Series: Lecture Notes in Computer Science 5125
• : Springer, 2008

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.

Keywords: real-time scheduling ; approximation algorithms

Reference

• DISOPT-CONF-2008-002
• View record in Web of Science

• URL: http://www.ru.is/icalp08/

Record created on 2008-08-21, modified on 2012-03-20