Abstract
This paper investigates the task of load balancing where the objective function is to minimize the pnorm of loads, for p\geq 1, in both static and incremental settings. We consider two closely related load balancing problems. In the bipartite matching problem we are given a bipartite graph G=(C\cup S, E) and the goal is to assign each client c\in C to a server s\in S so that the pnorm of assignment loads on S is minimized.
In the graph orientation problem the goal is to orient (direct) the edges of a given undirected graph while minimizing the pnorm of the outdegrees. The graph orientation problem is a special case of the bipartite matching problem, but less complex, which leads to simpler algorithms.
For the graph orientation problem we show that the celebrated ChibaNishizeki peeling algorithm provides a simple linear time load balancing scheme whose output is an orientation that is 2competitive, in a pnorm sense, for all p\geq 1. For the bipartite matching problem we first provide an offline algorithm that computes an optimal assignment. We then extend this solution to the online bipartite matching problem with reassignments, where vertices from C arrive in an online fashion together with their corresponding edges, and we are allowed to reassign an amortized O(1) vertices from C each time a new vertex arrives. In this online scenario we show how to maintain a single assignment that is 8competitive, in a pnorm sense, for all p\geq 1.
BibTeX  Entry
@InProceedings{bernstein_et_al:LIPIcs:2017:8200,
author = {Aaron Bernstein and Tsvi Kopelowitz and Seth Pettie and Ely Porat and Clifford Stein},
title = {{Simultaneously Load Balancing for Every pnorm, With Reassignments}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {51:151:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770293},
ISSN = {18688969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8200},
URN = {urn:nbn:de:0030drops82009},
doi = {10.4230/LIPIcs.ITCS.2017.51},
annote = {Keywords: Online Matching, Graph Orientation, Minmizing the pnorm}
}
Keywords: 

Online Matching, Graph Orientation, Minmizing the pnorm 
Collection: 

8th Innovations in Theoretical Computer Science Conference (ITCS 2017) 
Issue Date: 

2017 
Date of publication: 

28.11.2017 