Abstract
In this paper we study two fullydynamic multidimensional vector load balancing problems with recourse. The adversary presents a stream of n job insertions and deletions, where each job j is a vector in ℝ^d_{≥ 0}. In the vector scheduling problem, the algorithm must maintain an assignment of the active jobs to m identical machines to minimize the makespan (maximum load on any dimension on any machine). In the vector bin packing problem, the algorithm must maintain an assignment of active jobs into a number of bins of unit capacity in all dimensions, to minimize the number of bins currently used. In both problems, the goal is to maintain solutions that are competitive against the optimal solution for the active set of jobs, at every time instant. The algorithm is allowed to change the assignment from time to time, with the secondary objective of minimizing the amortized recourse, which is the average cardinality of the change of the assignment per update to the instance.
For the vector scheduling problem, we present two simple algorithms. The first is a randomized algorithm with an O(1) amortized recourse and an O(log d/log log d) competitive ratio against oblivious adversaries. The second algorithm is a deterministic algorithm that is competitive against adaptive adversaries but with a slightly higher competitive ratio of O(log d) and a perjob recourse guarantee bounded by Õ(log n + log d log OPT). We also prove a sharper instancedependent recourse guarantee for the deterministic algorithm.
For the vector bin packing problem, we make the socalled small jobs assumption that the size of all jobs in all the coordinates is O(1/log d) and present a simple O(1)competitive algorithm with O(log n) recourse against oblivious adversaries.
For both problems, the main challenge is to determine when and how to migrate jobs to maintain competitive solutions. Our central idea is that for each job, we make these decisions based only on the active set of jobs that are "earlier" than this job in some ordering ≺ of the jobs.
BibTeX  Entry
@InProceedings{gupta_et_al:LIPIcs.ITCS.2023.65,
author = {Gupta, Varun and Krishnaswamy, Ravishankar and Sandeep, Sai and Sundaresan, Janani},
title = {{Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {65:165:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17568},
URN = {urn:nbn:de:0030drops175685},
doi = {10.4230/LIPIcs.ITCS.2023.65},
annote = {Keywords: Vector Scheduling, Vector Load Balancing}
}
Keywords: 

Vector Scheduling, Vector Load Balancing 
Collection: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023) 
Issue Date: 

2023 
Date of publication: 

01.02.2023 