We consider a NP-hard resource allocation problem of allocating a set of resources to meet demands over a time period at the minimum cost. Each resource has a start time, finish time, availability and cost. The objective of the problem is to assign resources to meet the demands so that the overall cost is minimum. It is necessary that only one resource contributes to the demand of a slot. This constraint will be referred to as single resource assignment (SRA) constraint. We would refer to the problem as the S_RA problem. So far, only 16-approximation to this problem is known. In this paper, we propose an algorithm with approximation ratio of 12.
Accepté le :
DOI : 10.1051/ro/2017035
Mots-clés : Resource allocation, scheduling, primal dual
@article{RO_2018__52_2_371_0,
author = {Mondal, Sakib A.},
title = {Resource allocation problem under single resource assignment},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {371--382},
publisher = {EDP-Sciences},
volume = {52},
number = {2},
year = {2018},
doi = {10.1051/ro/2017035},
zbl = {1400.68262},
mrnumber = {3817471},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro/2017035/}
}
TY - JOUR AU - Mondal, Sakib A. TI - Resource allocation problem under single resource assignment JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2018 SP - 371 EP - 382 VL - 52 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2017035/ DO - 10.1051/ro/2017035 LA - en ID - RO_2018__52_2_371_0 ER -
%0 Journal Article %A Mondal, Sakib A. %T Resource allocation problem under single resource assignment %J RAIRO - Operations Research - Recherche Opérationnelle %D 2018 %P 371-382 %V 52 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2017035/ %R 10.1051/ro/2017035 %G en %F RO_2018__52_2_371_0
Mondal, Sakib A. Resource allocation problem under single resource assignment. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 2, pp. 371-382. doi : 10.1051/ro/2017035. http://www.numdam.org/articles/10.1051/ro/2017035/
[1] and , A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem, in Proc. Symp. Discrete Algorithms (2015) 1491–1505 | DOI | MR | Zbl
[2] , and , When trees collide: An approximation algorithm for the generalized steiner problem on networks. SIAM J. Comput. 24 (1995) 440–456 | DOI | MR | Zbl
[3] , , and , A Mazing ϵ Approximation for Unsplittable Flow on a Path, in Proc. Symp. Discrete Algorithms (2014) 26–41 | DOI | MR | Zbl
[4] , , and , A quasi-PTAS for unsplittable flow on line graphs, in Proc. Symp. Theory Comput. (2006) 721–729 | DOI | MR | Zbl
[5] , , , and , A unified approach to approximating resource allocation and scheduling. J. ACM 48 (2001) 1069–1090 | DOI | MR | Zbl
[6] and , A linear time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2 (1981) 198–203 | DOI | MR | Zbl
[7] , and , A constant factor approximation algorithm for unsplittable flow on paths, in Proc. Symp. Found. Comput. Sci. (2011) 47–56 | MR | Zbl
[8] and , Primal-dual schema for capacitated covering problems, in Proc. Confer. Integer Program. Combinatorial Optimiz. (2008) 288–302 | MR | Zbl
[9] , , and , Strengthening integrality gaps for capacitated network design and covering problems, in Proc. Symp. Discrete Algorithms (2000) 106–115 | MR | Zbl
[10] , and On column-restricted and priority covering integer programs, in Proc. Confer. Integer Program. Combinatorial Optimiz. (2010) 355–368 | MR | Zbl
[11] , , , and , Reusable Resource Scheduling via Colored Interval Covering, in Proc. Inter. Confer. Parallel and Distributed Processing (2016) 1003–1012
[12] , , , and , Minimum cost resource allocation for meeting job requirements, in Proc. IEEE Inter. Parallel and Distributed Processing Symposium (2011) 14–23
[13] , , and , Resource Allocation for Covering Time Varying Demands, in Proc. Europ. Symp. Algorithms (2011) 543–554 | MR | Zbl
[14] , and , Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms 3 (2007) | DOI | MR | Zbl
[15] , A greedy heuristic for the setcovering problem. Math. Oper. Res. 4 (1979) 233–235 | DOI | MR | Zbl
[16] and , Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22 (1975) 463–468 | DOI | MR | Zbl
[17] and , Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48 (1975) 274–296 | DOI | MR | Zbl
[18] ,Reducibility among combinatorial problems. In Complexity of Computer Computations, edited by and Plenum Press (1972) 85–103 | DOI | MR | Zbl
[19] , Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4 (1979) 339–356 | DOI | MR | Zbl
Cité par Sources :
