Loading...
conference paper
A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation
2008
Automata, Languages and Programming (ICALP'08)
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.
Loading...
Name
RTS-PTAS-ICALP08-TechReport.pdf
Access type
openaccess
Size
158.69 KB
Format
Adobe PDF
Checksum (MD5)
64484616bfe953e6560f5c441cf9d856