TY - GEN

T1 - Simultaneously load balancing for every p-norm, with reassignments

AU - Bernstein, Aaron

AU - Kopelowitz, Tsvi

AU - Pettie, Seth

AU - Porat, Ely

AU - Stein, Clifford

N1 - Funding Information:
∗ Research supported in part by NSF grants CCF-1421161, CCF-1514383, and CCF-1637546.
Funding Information:
NSF grants CCF-1421161, CCF-1514383, and CCF-1637546

PY - 2017/11/1

Y1 - 2017/11/1

N2 - the This paper investigates the task of load balancing where the objective function is to minimize The p-norm of loads, for p > 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 [ S,E) and the goal is to assign each client c € C to a server s € 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 ≥ 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 ≥ 1.

AB - the This paper investigates the task of load balancing where the objective function is to minimize The p-norm of loads, for p > 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 [ S,E) and the goal is to assign each client c € C to a server s € 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 ≥ 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 ≥ 1.

KW - Graph Orientation

KW - Minimizing the p-norm

KW - Online Matching

UR - http://www.scopus.com/inward/record.url?scp=85038588151&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85038588151&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ITCS.2017.51

DO - 10.4230/LIPIcs.ITCS.2017.51

M3 - Conference contribution

AN - SCOPUS:85038588151

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017

A2 - Papadimitriou, Christos H.

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017

Y2 - 9 January 2017 through 11 January 2017

ER -