Simultaneously load balancing for every p-norm, with reassignments

Aaron Bernstein, Tsvi Kopelowitz, Seth Pettie, Ely Porat, Clifford Stein

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication8th Innovations in Theoretical Computer Science Conference, ITCS 2017
EditorsChristos H. Papadimitriou
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770293
DOIs
StatePublished - Nov 1 2017
Externally publishedYes
Event8th Innovations in Theoretical Computer Science Conference, ITCS 2017 - Berkeley, United States
Duration: Jan 9 2017Jan 11 2017

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume67
ISSN (Print)1868-8969

Other

Other8th Innovations in Theoretical Computer Science Conference, ITCS 2017
Country/TerritoryUnited States
CityBerkeley
Period1/9/171/11/17

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Graph Orientation
  • Minimizing the p-norm
  • Online Matching

Fingerprint

Dive into the research topics of 'Simultaneously load balancing for every p-norm, with reassignments'. Together they form a unique fingerprint.

Cite this