Chakrabarty, Deeparnab ;
Swamy, Chaitanya
Simpler and Better Algorithms for MinimumNorm Load Balancing
Abstract
Recently, Chakrabarty and Swamy (STOC 2019) introduced the minimumnorm loadbalancing problem on unrelated machines, wherein we are given a set J of jobs that need to be scheduled on a set of m unrelated machines, and a monotone, symmetric norm; We seek an assignment sigma: J > [m] that minimizes the norm of the resulting load vector load_{sigma} in R_+^m, where load_{sigma}(i) is the load on machine i under the assignment sigma. Besides capturing all l_p norms, symmetric norms also capture other norms of interest including topl norms, and ordered norms. Chakrabarty and Swamy (STOC 2019) give a (38+epsilon)approximation algorithm for this problem via a general framework they develop for minimumnorm optimization that proceeds by first carefully reducing this problem (in a series of steps) to a problem called minmax ordered load balancing, and then devising a socalled deterministic oblivious LProunding algorithm for ordered load balancing.
We give a direct, and simple 4+epsilonapproximation algorithm for the minimumnorm load balancing based on rounding a (nearoptimal) solution to a novel convexprogramming relaxation for the problem. Whereas the natural convex program encoding minimumnorm load balancing problem has a large nonconstant integrality gap, we show that this issue can be remedied by including a key constraint that bounds the "norm of the jobcost vector." Our techniques also yield a (essentially) 4approximation for: (a) multinorm load balancing, wherein we are given multiple monotone symmetric norms, and we seek an assignment respecting a given budget for each norm; (b) the best simultaneous approximation factor achievable for all symmetric norms for a given instance.
BibTeX  Entry
@InProceedings{chakrabarty_et_al:LIPIcs:2019:11148,
author = {Deeparnab Chakrabarty and Chaitanya Swamy},
title = {{Simpler and Better Algorithms for MinimumNorm Load Balancing}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {27:127:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11148},
URN = {urn:nbn:de:0030drops111488},
doi = {10.4230/LIPIcs.ESA.2019.27},
annote = {Keywords: Approximation Algorithms}
}
06.09.2019
Keywords: 

Approximation Algorithms 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

06.09.2019 