License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.51
URN: urn:nbn:de:0030-drops-82009
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8200/
Bernstein, Aaron ;
Kopelowitz, Tsvi ;
Pettie, Seth ;
Porat, Ely ;
Stein, Clifford
Simultaneously Load Balancing for Every p-norm, With Reassignments
Abstract
This paper investigates the task of load balancing where the objective function is to minimize the p-norm 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 p-norm 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 p-norm of the out-degrees. 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 Chiba-Nishizeki peeling algorithm provides a simple linear time load balancing scheme whose output is an orientation that is 2-competitive, in a p-norm 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 8-competitive, in a p-norm 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 p-norm, With Reassignments}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {51:1--51:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-029-3},
ISSN = {1868-8969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8200},
URN = {urn:nbn:de:0030-drops-82009},
doi = {10.4230/LIPIcs.ITCS.2017.51},
annote = {Keywords: Online Matching, Graph Orientation, Minmizing the p-norm}
}
|
Keywords: |
|
Online Matching, Graph Orientation, Minmizing the p-norm |
|
Collection: |
|
8th Innovations in Theoretical Computer Science Conference (ITCS 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
28.11.2017 |
