Running summarizing tools on a new article

Check the paper below, then start its synthesis.


A Unified Rounding Algorithm For Unrelated Machines Scheduling Problems

Nikhil R. Devanur (Microsoft (United States)), Janardhan Kulkarni (Microsoft (United States))

ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
License: not stated (all rights reserved)

Abstract: The rise of cloud computing platforms has led to the study of many scheduling problems. Towards this, general algorithmic techniques that are applicable to a wide range of problems are highly valuable. We develop one such technique by a temporal generalization of the rounding algorithm of \citetShmoysT93 for the generalized assignment problem. Our algorithm gives a bi-criteria approximation algorithm for a problem we introduce, called the generalized interval scheduling problem, on unrelated machines. The problem allows for each job, a specification of a collection of intervals on each machine, with the constraint that the job must be completely processed in one of the given intervals on a single machine. The assignment costs and the processing lengths are interval dependent. Next we show how to get improved approximation factors for several classical scheduling problems, involving energy, $\ell_p$-norms of completion time, tardiness, and general delay costs by giving a reduction from these problems to the generalized interval scheduling problem with an appropriately defined assignment cost.

Published on 11 Jul. 2018