Abstract
Motivated by the classic Generalized Assignment Problem, we consider the Graph Balancing problem in the presence of orientation costs: given an undirected multigraph G=(V,E) equipped with edge weights and orientation costs on the edges, the goal is to find an orientation of the edges that minimizes both the maximum weight of edges oriented toward any vertex (makespan) and total orientation cost. We present a general framework for minimizing makespan in the presence of costs that allows us to: (1) achieve bicriteria approximations for the Graph Balancing problem that capture known previous results (ShmoysTardos [Math. Progrm. '93], EbenlendrKrcálSgall [Algorithmica '14], and WangSitters [Inf. Process. Lett. '16]); and (2) achieve bicriteria approximations for extensions of the Graph Balancing problem that admit hyperedges and unrelated weights. Our framework is based on a remarkably simple rounding of a strengthened linear relaxation. We complement the above by presenting bicriteria lower bounds with respect to the linear programming relaxations we use that show that a loss in the total orientation cost is required if one aims for an approximation better than 2 in the makespan.
BibTeX  Entry
@InProceedings{schwartz_et_al:LIPIcs:2019:11203,
author = {Roy Schwartz and Ran Yeheskel},
title = {{Graph Balancing with Orientation Costs}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {82:182:15},
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/11203},
URN = {urn:nbn:de:0030drops112034},
doi = {10.4230/LIPIcs.ESA.2019.82},
annote = {Keywords: Graph Balancing, Generalized Assignment Problem}
}
Keywords: 

Graph Balancing, Generalized Assignment Problem 
Collection: 

27th Annual European Symposium on Algorithms (ESA 2019) 
Issue Date: 

2019 
Date of publication: 

06.09.2019 