1 Search Results for "Nguyen, Trung Thanh"

Document
DOI: 10.4230/LIPIcs.ISAAC.2020.14
Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs

Authors: Trung Thanh Nguyen and Jörg Rothe

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
We study a generalized version of the load balancing problem on unrelated machines with cost constraints: Given a set of m machines (of certain types) and a set of n jobs, each job j processed on machine i requires p_{i,j} time units and incurs a cost c_{i,j}, and the goal is to find a schedule of jobs to machines, which is defined as an ordered partition of n jobs into m disjoint subsets, in such a way that some objective function of the vector of the completion times of the machines is optimized, subject to the constraint that the total costs by the schedule must be within a given budget B. Motivated by recent results from the literature, our focus is on the case when the number of machine types is a fixed constant and we develop a bi-criteria approximation scheme for the studied problem. Our result generalizes several known results for certain special cases, such as the case with identical machines, or the case with a constant number of machines with cost constraints. Building on the elegant technique recently proposed by Jansen and Maack [K. Jansen and M. Maack, 2019], we construct a more general approach that can be used to derive approximation schemes to a wider class of load balancing problems with constraints.
Cite as

Trung Thanh Nguyen and Jörg Rothe. Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nguyen_et_al:LIPIcs.ISAAC.2020.14,
  author =	{Nguyen, Trung Thanh and Rothe, J\"{o}rg},
  title =	{{Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{14:1--14:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.14},
  URN =		{urn:nbn:de:0030-drops-133582},
  doi =		{10.4230/LIPIcs.ISAAC.2020.14},
  annote =	{Keywords: bi-criteria approximation algorithm, polynomial-time approximation algorithm, load balancing, machine scheduling}
}
  • Refine by Author
  • 1 Nguyen, Trung Thanh
  • 1 Rothe, Jörg

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis

  • Refine by Keyword
  • 1 bi-criteria approximation algorithm
  • 1 load balancing
  • 1 machine scheduling
  • 1 polynomial-time approximation algorithm

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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