1 Search Results for "Yeheskel, Ran"

Document

DOI: 10.4230/LIPIcs.ESA.2019.82

Graph Balancing with Orientation Costs

Authors: Roy Schwartz and Ran Yeheskel

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

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.

Cite as

Roy Schwartz and Ran Yeheskel. Graph Balancing with Orientation Costs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 82:1-82:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{schwartz_et_al:LIPIcs.ESA.2019.82,
  author =	{Schwartz, Roy and Yeheskel, Ran},
  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 =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.82},
  URN =		{urn:nbn:de:0030-drops-112034},
  doi =		{10.4230/LIPIcs.ESA.2019.82},
  annote =	{Keywords: Graph Balancing, Generalized Assignment Problem}
}

Refine by Author
1 Schwartz, Roy
1 Yeheskel, Ran

Refine by Classification
1 Mathematics of computing → Approximation algorithms
1 Theory of computation → Scheduling algorithms

Refine by Keyword
1 Generalized Assignment Problem
1 Graph Balancing

Refine by Type
1 document

Refine by Publication Year
1 2019

1 Search Results for "Yeheskel, Ran"

Graph Balancing with Orientation Costs

Abstract

Cite as

Thanks for your feedback!

Could not send message