*Result*: Approximating Real-Time Scheduling on Identical Machines.

*We study the problem of assigning <italic>n</italic> tasks to <italic>m</italic> identical parallel machines in the real-time scheduling setting, where each task recurrently releases jobs that must be completed by their deadlines. The goal is to find a partition of the task set over the machines such that each job that is released by a task can meet its deadline. Since this problem is co-NP-hard, the focus is on finding <italic>α</italic>-approximation algorithms in the resource augmentation setting, i.e., finding a feasible partition on machines running at speed <italic>α</italic> ≥ 1, if some feasible partition exists on unit-speed machines. Recently, Chen and Chakraborty gave a polynomial-time approximation scheme if the ratio of the largest to the smallest relative deadline of the tasks, <italic>λ</italic>, is bounded by a constant. However, their algorithm has a super-exponential dependence on <italic>λ</italic> and hence does not extend to larger values of <italic>λ</italic>. Our main contribution is to design an approximation scheme with a substantially improved running-time dependence on <italic>λ</italic>. In particular, our algorithm depends exponentially on log<italic>λ</italic> and hence has quasi-polynomial running time even if <italic>λ</italic> is polynomially bounded. This improvement is based on exploiting various structural properties of approximate demand bound functions in different ways, which might be of independent interest. [ABSTRACT FROM AUTHOR]

Copyright of LATIN 2014: Theoretical Informatics is the property of Springer eBooks and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)*