Skip to main content

Online load balancing on related machines

Publication ,  Conference
Im, S; Panigrahi, D; Kell, N; Shadloo, M
Published in: Proceedings of the Annual ACM Symposium on Theory of Computing
June 20, 2018

We give a constant-competitive algorithm for the problem of assigning jobs online to machines with non-uniform speed (called related machines) so as to optimize any ℓq-norm of the machine loads. Previously, such a result was only known for the special case of the makespan, or ℓ∞. norm. We also extend these results to obtain tight bounds for the problem of vector scheduling on related machines, where no results were previously known even for the makespan norm. To obtain our results, we employ a convex relaxation of the ℓq-norm objective and use a continuous greedy algorithm to solve this convex program online. To round the fractional solution, we then use a novel restructuring of the instance that we call machine smoothing. This is a generic tool that reduces a problem on related machines to a set of problem instances on identical machines, and we hope it will be useful in other settings with non-uniform machine speeds as well.

Duke Scholars

Published In

Proceedings of the Annual ACM Symposium on Theory of Computing

DOI

ISSN

0737-8017

Publication Date

June 20, 2018

Start / End Page

978 / 989
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Im, S., Panigrahi, D., Kell, N., & Shadloo, M. (2018). Online load balancing on related machines. In Proceedings of the Annual ACM Symposium on Theory of Computing (pp. 978–989). https://doi.org/10.1145/3188745.3188966
Im, S., D. Panigrahi, N. Kell, and M. Shadloo. “Online load balancing on related machines.” In Proceedings of the Annual ACM Symposium on Theory of Computing, 978–89, 2018. https://doi.org/10.1145/3188745.3188966.
Im S, Panigrahi D, Kell N, Shadloo M. Online load balancing on related machines. In: Proceedings of the Annual ACM Symposium on Theory of Computing. 2018. p. 978–89.
Im, S., et al. “Online load balancing on related machines.” Proceedings of the Annual ACM Symposium on Theory of Computing, 2018, pp. 978–89. Scopus, doi:10.1145/3188745.3188966.
Im S, Panigrahi D, Kell N, Shadloo M. Online load balancing on related machines. Proceedings of the Annual ACM Symposium on Theory of Computing. 2018. p. 978–989.

Published In

Proceedings of the Annual ACM Symposium on Theory of Computing

DOI

ISSN

0737-8017

Publication Date

June 20, 2018

Start / End Page

978 / 989