Randomized algorithms for online vector load balancing

Conference Paper

We study randomized algorithms for the online vector bin packing and vector scheduling problems. For vector bin packing, we achieve a competitive ratio of ~O(d1=B), where d is the number of dimensions and B the size of a bin. This improves the previous bound of Õ(d1B)) by a polynomial factor, and is tight up to logarithmic factors. For vector scheduling, we show a lower bound of ( log d log log d ) on the competitive ratio of randomized algorithms, which is the first result for randomized algorithms and is asymptotically tight. Finally, we analyze the widely used "power of two choices' algorithm for vector scheduling, and show that its competitive ratio is O(log log n+ log d log log d ), which is optimal up to the additive O(log log n) term that also appears in the scalar version of this algorithm.

Full Text

Duke Authors

Cited Authors

  • Azar, Y; Cohen, IR; Panigrahi, D

Published Date

  • January 1, 2018

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 990 - 991

International Standard Book Number 13 (ISBN-13)

  • 9781611975031

Digital Object Identifier (DOI)

  • 10.1137/1.9781611975031.63

Citation Source

  • Scopus