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...
Lưu vào:
| Tác giả chính: | , |
|---|---|
| Định dạng: | Bài trích |
| Ngôn ngữ: | eng |
| Nhà xuất bản: |
Theoretical Computer Science
2021
|
| Chủ đề: | |
| Truy cập trực tuyến: | 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 |
| Từ khóa: |
Thêm từ khóa
Không có từ khóa, Hãy là người đầu tiên đánh dấu biểu ghi này!
|
| 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.891695 |