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.ESA.2019.82
URN: urn:nbn:de:0030-drops-112034
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11203/
Go to the corresponding LIPIcs Volume Portal

Schwartz, Roy ; Yeheskel, Ran

Graph Balancing with Orientation Costs

pdf-format:
LIPIcs-ESA-2019-82.pdf (0.6 MB)

Abstract

Motivated by the classic Generalized Assignment Problem, we consider the Graph Balancing problem in the presence of orientation costs: given an undirected multi-graph 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 (Shmoys-Tardos [Math. Progrm. '93], Ebenlendr-Krcál-Sgall [Algorithmica '14], and Wang-Sitters [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:1--82:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11203},
  URN =		{urn:nbn:de:0030-drops-112034},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI