Resource allocation problem under single resource assignment
RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 2, pp. 371-382.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017035
Classification : 68W25, 90B35, 68R01
Mots-clés : Resource allocation, scheduling, primal dual
Mondal, Sakib A. 1

1 
@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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ro/2017035/

[1] A. Adamaszek and A. Wiese, A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem, in Proc. Symp. Discrete Algorithms (2015) 1491–1505 | DOI | MR | Zbl

[2] A. Agrawal, P.N. Klein and R. Ravi, When trees collide: An approximation algorithm for the generalized steiner problem on networks. SIAM J. Comput. 24 (1995) 440–456 | DOI | MR | Zbl

[3] A. Anagnostopoulos, F. Grandoni, S. Leonardi and A. Wiese, A Mazing ϵ Approximation for Unsplittable Flow on a Path, in Proc. Symp. Discrete Algorithms (2014) 26–41 | DOI | MR | Zbl

[4] N. Bansal, A. Chakrabarti, A. Epstein and B. Schieber, A quasi-PTAS for unsplittable flow on line graphs, in Proc. Symp. Theory Comput. (2006) 721–729 | DOI | MR | Zbl

[5] A. Bar-Noy, R. Bar-Yehuda, A. Freund, J. Naor and B. Schieber, A unified approach to approximating resource allocation and scheduling. J. ACM 48 (2001) 1069–1090 | DOI | MR | Zbl

[6] R. Bar-Yehuda and S. Even, A linear time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2 (1981) 198–203 | DOI | MR | Zbl

[7] P. Bonsma, J. Schulz and A. Wiese, A constant factor approximation algorithm for unsplittable flow on paths, in Proc. Symp. Found. Comput. Sci. (2011) 47–56 | MR | Zbl

[8] T. Carnes and D. Shmoys, Primal-dual schema for capacitated covering problems, in Proc. Confer. Integer Program. Combinatorial Optimiz. (2008) 288–302 | MR | Zbl

[9] R.D. Carr, L. Fleischer, V.J. Leung and C.A. Phillips, Strengthening integrality gaps for capacitated network design and covering problems, in Proc. Symp. Discrete Algorithms (2000) 106–115 | MR | Zbl

[10] D. Chakrabarty, E. Grant and J. Könemann. On column-restricted and priority covering integer programs, in Proc. Confer. Integer Program. Combinatorial Optimiz. (2010) 355–368 | MR | Zbl

[11] V. Chakaravarthy, S. Kenkre, S.A. Mondal, V. Pandit and Y. Sabharwal, Reusable Resource Scheduling via Colored Interval Covering, in Proc. Inter. Confer. Parallel and Distributed Processing (2016) 1003–1012

[12] V. Chakaravarthy, A. Kumar, G. Parija, S. Roy and Y. Sabharwal, Minimum cost resource allocation for meeting job requirements, in Proc. IEEE Inter. Parallel and Distributed Processing Symposium (2011) 14–23

[13] V. Chakaravarthy, A. Kumar, S. Roy and Y. Sabharwal, Resource Allocation for Covering Time Varying Demands, in Proc. Europ. Symp. Algorithms (2011) 543–554 | MR | Zbl

[14] C. Chekuri, M. Mydlarz and F. Shepherd, Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms 3 (2007) | DOI | MR | Zbl

[15] V. Chvátal, A greedy heuristic for the setcovering problem. Math. Oper. Res. 4 (1979) 233–235 | DOI | MR | Zbl

[16] O. Ibarra and C. Kim, Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22 (1975) 463–468 | DOI | MR | Zbl

[17] K. Jain and V. Vazirani, 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] R. Karp,Reducibility among combinatorial problems. In Complexity of Computer Computations, edited by R. Miller and J. Thatcher. Plenum Press (1972) 85–103 | DOI | MR | Zbl

[19] E.L. Lawler, Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4 (1979) 339–356 | DOI | MR | Zbl

Cité par Sources :