Cover Image

Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints

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 time units and incurs a cost , and the goal is to find a schedule of jobs to machine...

Full description

Saved in:
Bibliographic Details
Main Authors: Trung Thanh Nguyen, Jörg Rothe
Format: Bài trích
Language:eng
Published: Theoretical Computer Science 2021
Subjects:
Bi-criteria approximation algorithm
Polynomial-time approximation algorithm
Load balancing
Online Access:https://www.sciencedirect.com/science/article/abs/pii/S030439752030726X?via%3Dihub
https://dlib.phenikaa-uni.edu.vn/handle/PNK/2839
https://doi.org/10.1016/j.tcs.2020.12.022
Tags: Add Tag
No Tags, Be the first to tag this record!
id oai:localhost:PNK-2839
record_format dspace
spelling oai:localhost:PNK-28392022-08-17T05:54:47Z Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints Trung Thanh Nguyen Jörg Rothe Bi-criteria approximation algorithm Polynomial-time approximation algorithm Load balancing 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 time units and incurs a cost , 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 [1], we construct a more general approach that can be used to derive approximation schemes for a wider class of load balancing problems with linear constraints. 2021-09-14T07:14:52Z 2021-09-14T07:14:52Z 2021 Bài trích https://www.sciencedirect.com/science/article/abs/pii/S030439752030726X?via%3Dihub https://dlib.phenikaa-uni.edu.vn/handle/PNK/2839 https://doi.org/10.1016/j.tcs.2020.12.022 eng Theoretical Computer Science
institution Digital Phenikaa
collection Digital Phenikaa
language eng
topic Bi-criteria approximation algorithm
Polynomial-time approximation algorithm
Load balancing
spellingShingle Bi-criteria approximation algorithm
Polynomial-time approximation algorithm
Load balancing
Trung Thanh Nguyen
Jörg Rothe
Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
description 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 time units and incurs a cost , 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 [1], we construct a more general approach that can be used to derive approximation schemes for a wider class of load balancing problems with linear constraints.
format Bài trích
author Trung Thanh Nguyen
Jörg Rothe
author_facet Trung Thanh Nguyen
Jörg Rothe
author_sort Trung Thanh Nguyen
title Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
title_short Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
title_full Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
title_fullStr Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
title_full_unstemmed Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
title_sort improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
publisher Theoretical Computer Science
publishDate 2021
url https://www.sciencedirect.com/science/article/abs/pii/S030439752030726X?via%3Dihub
https://dlib.phenikaa-uni.edu.vn/handle/PNK/2839
https://doi.org/10.1016/j.tcs.2020.12.022
_version_ 1751856265147973632
score 8.881002

Similar Items