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 -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.
Accepté le :
DOI : 10.1051/ro/2015010
Mots clés : Prize-collecting, call control, approximation algorithms
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro/2015010/
, , and , Call Control in Rings. Algorithmica 47 (2007) 217–238. | DOI | MR | Zbl
, , and , Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput. 40 (2011) 309–332. | DOI | MR | Zbl
and , 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
, , and , A logarithmic approximation for unsplittable flow on line graphs. ACM Trans. Algorithms 10 (2014) article no. 1. | DOI | MR | Zbl
, , , and , 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
, and , A constant-factor approximation algorithm for unsplittable flow on paths. SIAM J. Comput. 43 (2014) 767–799. | DOI | MR | Zbl
and , On the -coloring of intervals. Discrete Appl. Math. 59 (1995) 225–235. | DOI | MR | Zbl
, , and , An improved approximation algorithm for resource allocation. ACM Trans. on Algorithms 7 (2011) article no. 48. | DOI | MR | Zbl
, , and , Approximation algorithms for the unsplittable flow problem. Algorithmica 47 (2007) 53–78. | DOI | MR | Zbl
, and , 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
, and , 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
and , Min sum clustering with penalties. Eur. J. Oper. Res. 206 (2010) 547–554. | DOI | MR | Zbl
, , 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 :
