Geodesic
The Prize-collecting Call Control Problem on Weighted Lines and Rings
Li, Weidong1 ; Li, Jianping1 ; Guan, Li1 ; Shi, Yaomin2
1 Yunnan University, Kunming 650091, P.R. China.
2 Chongqing Radio & TV University, Chongqing, P.R. China.
RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 39-46

Voir la notice de l'article provenant de la source Numdam

Given a set of request calls with different demands and penalty costs, the prize-collecting call control (PCCC) problem is to minimize the sum of the maximum load on the edges and the total penalty cost of the rejected calls. In this paper, we prove that the PCCC problem on weighted lines is NP-hard even for special cases, and design a 1.582-approximation algorithm using a randomized rounding technique. In addition, we consider some special cases of the PCCC problem on weighted lines and rings.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2015010
Classification : 90C27
Keywords: Prize-collecting, call control, approximation algorithms

Li, Weidong 1 ; Li, Jianping 1 ; Guan, Li 1 ; Shi, Yaomin 2

1 Yunnan University, Kunming 650091, P.R. China.
2 Chongqing Radio & TV University, Chongqing, P.R. China. 
@article{RO_2016__50_1_39_0,
     author = {Li, Weidong and Li, Jianping and Guan, Li and Shi, Yaomin},
     title = {The {Prize-collecting} {Call} {Control} {Problem} on {Weighted} {Lines} and {Rings}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {39--46},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     year = {2016},
     doi = {10.1051/ro/2015010},
     mrnumber = {3460661},
     zbl = {1333.90110},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2015010/}
}
TY  - JOUR
AU  - Li, Weidong
AU  - Li, Jianping
AU  - Guan, Li
AU  - Shi, Yaomin
TI  - The Prize-collecting Call Control Problem on Weighted Lines and Rings
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 39
EP  - 46
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro/2015010/
DO  - 10.1051/ro/2015010
LA  - en
ID  - RO_2016__50_1_39_0
ER  - 
%0 Journal Article
%A Li, Weidong
%A Li, Jianping
%A Guan, Li
%A Shi, Yaomin
%T The Prize-collecting Call Control Problem on Weighted Lines and Rings
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 39-46
%V 50
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro/2015010/
%R 10.1051/ro/2015010
%G en
%F RO_2016__50_1_39_0
Li, Weidong; Li, Jianping; Guan, Li; Shi, Yaomin. The Prize-collecting Call Control Problem on Weighted Lines and Rings. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 1, pp. 39-46. doi: 10.1051/ro/2015010

Cité par Sources :