1 Search Results for "Ott, Sebastian"

Document
DOI: 10.4230/LIPIcs.ESA.2016.49
A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges

Authors: Chien-Chung Huang and Sebastian Ott

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Makespan minimization in restricted assignment (R|p_{ij} in {p_j, infinity}|C_{max}) is a classical problem in the field of machine scheduling. In a landmark paper, [Lenstra, Shmoys, and Tardos, Math. Progr. 1990] gave a 2-approximation algorithm and proved that the problem cannot be approximated within 1.5 unless P=NP. The upper and lower bounds of the problem have been essentially unimproved in the intervening 25 years, despite several remarkable successful attempts in some special cases of the problem recently. In this paper, we consider a special case called graph-balancing with light hyper edges, where heavy jobs can be assigned to at most two machines while light jobs can be assigned to any number of machines. For this case, we present algorithms with approximation ratios strictly better than 2. Specifically, - Two job sizes: Suppose that light jobs have weight w and heavy jobs have weight W, and w < W. We give a 1.5-approximation algorithm (note that the current 1.5 lower bound is established in an even more restrictive setting). Indeed, depending on the specific values of w and W, sometimes our algorithm guarantees sub-1.5 approximation ratios. - Arbitrary job sizes: Suppose that W is the largest given weight, heavy jobs have weights in the range of (beta W, W], where 4/7 <= beta < 1, and light jobs have weights in the range of (0,beta W]. We present a (5/3+beta/3)-approximation algorithm. Our algorithms are purely combinatorial, without the need of solving a linear program as required in most other known approaches.
Cite as

Chien-Chung Huang and Sebastian Ott. A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ESA.2016.49,
  author =	{Huang, Chien-Chung and Ott, Sebastian},
  title =	{{A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{49:1--49:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.49},
  URN =		{urn:nbn:de:0030-drops-63919},
  doi =		{10.4230/LIPIcs.ESA.2016.49},
  annote =	{Keywords: Approximation Algorithms, Machine Scheduling, Graph Balancing, Combinatorial Algorithms}
}
  • Refine by Author
  • 1 Huang, Chien-Chung
  • 1 Ott, Sebastian

  • Refine by Classification

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Combinatorial Algorithms
  • 1 Graph Balancing
  • 1 Machine Scheduling

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact