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.

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
Mots-clés : 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://archive.numdam.org/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://archive.numdam.org/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://archive.numdam.org/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. http://archive.numdam.org/articles/10.1051/ro/2015010/

U. Adamy, C. Ambuhl, R.S. Anand and T. Erlebach, Call Control in Rings. Algorithmica 47 (2007) 217–238. | DOI | MR | Zbl

A. Archer, M.H. Bateni, M.T. Hajiaghayi and H. Karloff, Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput. 40 (2011) 309–332. | DOI | MR | Zbl

Y. Azar and O. Regev, Combinatorial algorithms for the unsplittable flow problem. Algorithmica 44 (2006) 49–66. | DOI | MR | Zbl

N. Bansal, A. Chakrabarti, A. Epstein and B. Schieber, A quasi-PTAS for unsplittable flow on line graphs, in Proc. of the thirty-eighth annual ACM Symposium on Theory of computing (STOC) (2006) 721–729. | MR | Zbl

N. Bansal, Z. Friggstad, R. Khandekar and M.R. Salavatipour, A logarithmic approximation for unsplittable flow on line graphs. ACM Trans. Algorithms 10 (2014) article no. 1. | DOI | MR | Zbl

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

M. Bateni, C. Chekuri, A. Ene, M.T. Hajiaghayi, N. Korula and D. Marx, Prize-collecting steiner problems on planar graphs, in Proc. of the 22nd annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2011) 1028–1049. | MR

P. Bonsma, J. Schulz and A. Wiese, A constant-factor approximation algorithm for unsplittable flow on paths. SIAM J. Comput. 43 (2014) 767–799. | DOI | MR | Zbl

M.C. Carlisle and E.L. Lloyd, On the k-coloring of intervals. Discrete Appl. Math. 59 (1995) 225–235. | DOI | MR | Zbl

G. Calinescu, A. Chakrabarti, H. Karloff and Y. Rabani, An improved approximation algorithm for resource allocation. ACM Trans. on Algorithms 7 (2011) article no. 48. | DOI | MR | Zbl

A. Chakrabarti, C. Chekuri, A. Kumar and A. Gupta, Approximation algorithms for the unsplittable flow problem. Algorithmica 47 (2007) 53–78. | DOI | MR | Zbl

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

C. Chekuri, A. Ene and N. Korula, Unsplittable flow in paths and trees and column-restricted packing integer programs, in Proc. of APPROX-RANDOM (2009) 42–55. | MR | Zbl

M.C. Costa, L. Letocart and F. Roupin, Minimal multicut and maximum integer multiflow: a survey. Eur. J. Oper. Res. 162 (2005) 55–69. | DOI | MR | Zbl

K. Elbassioni, N. Garg, D. Gupta, A. Kumar, V. Narula and A. Pal, Approximation algorithms for the unsplittable flow problem on paths and trees. Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (2012) 267–275. | MR

M.R. Garey and D.S. Johnson, Computer and Intractability: A guide to the theory of NP-completeness. W.H. Freeman and Company. San Francisco (1979). | MR | Zbl

R. Hassin and E. Or, Min sum clustering with penalties. Eur. J. Oper. Res. 206 (2010) 547–554. | DOI | MR | Zbl

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

J.M. Kleinberg, Single-source unsplittable flow, in Proc. of 37th Annual Symposium on Foundation of Computer Science (FOCS) (1996) 68–77. | MR

W. Li, Y. Shi, Li. Guan and J. Li, The prize-collecting call control problem, in Proc. of 2nd International Conference on Information Science and Engineering (2010) 1609–1612.

Cité par Sources :