Abstract
Given a graph G = (V,E) with a cost on each edge in E and a prize at each vertex in V, and a target set V′ ⊆ V, the Prize Collecting Steiner Tree (PCST) problem is to find a tree T interconnecting vertices in V′ that has minimum total costs on edges and maximum total prizes at vertices in T. This problem is NP-hard in general, and it is polynomial-time solvable when graphs G are restricted to 2-trees. In this paper, we study how to deal with PCST problem with uncertain costs and prizes. We assume that edge e could be included in T by paying cost \(x_e\in[c_e^-,c_e^+]\) while taking risk \(\frac{ c_e^+-x_e}{ c_e^+-c_e^-}\) of losing e, and vertex v could be awarded prize \(p_v\in [p_v^-,p_v^+]\) while taking risk \(\frac{ y_v-p_v^-}{p_v^+-p_v^-}\) of losing the prize. We establish two risk models for the PCST problem, one minimizing the maximum risk over edges and vertices in T and the other minimizing the sum of risks. Both models are subject to upper bounds on the budget for constructing a tree. We propose two polynomial-time algorithms for these problems on 2-trees, respectively. Our study shows that the risk models have advantages over the tradional robust optimization model, which yields NP-hard problems even if the original optimization problems are polynomial-time solvable.
Supported in part by NNSF of China under Grant No. 10531070, 10771209, 10721101,10928102 and Chinese Academy of Sciences under Grant No. kjcx-yw-s7. P 4 Project Grant Center for Research and Applications in Plasma Physics and Pulsed Power Technology, PBCT-Chile-ACT 26, CONICYT; and Dirección de Programas de Investigación, Universidad de Talca, Chile.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aron, I.D., Hentenryck, P.V.: On the complexity of the robust spanning tree problem with interval data. Operations Research Letters 32, 36–40 (2004)
Balas, E.: The prize cllecting travelling salesman problem. Network 19, 621–636 (1989)
Chen, G., Xue, G.: A PTAS for weight constrained Steiner trees in series parallel graphs. Theoretical Computer Science 304, 237–247 (2003)
Chen, X.J., Hu, J., Hu, X.D.: The polynomial solvable minimum risk spanning tree problem with interval data. European Journal Operational Research 198, 43–46 (2009)
Feofiloff, P., Fernandes, C.G., Ferreira, C.E., Pina, J.C.: Primal-dual approximation algorithms for the prize collecting Steiner tree problem. Information Processing Letters 103(5), 195–202 (2007)
Hu, J.: Minimizing maximum risk for fair network connection with interval data. Acta Mathematicae Applicatae Sinica 26(1), 33–40 (2010)
Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem, Amsterdam (1992)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Tatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
Klau, G., Ljubic, I., Mutzel, P., Pferschy, U., Weiskircher, R.: The fractional prize collecting Steiner tree problem on trees. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 691–702. Springer, Heidelberg (2003)
Lucena, A., Resende, M.G.: Strong lower bounds for the prize collecting Steiner tree problem in graphs. Discrete Applied Mathematics 141, 277–294 (1979)
Megiddo, N.: Combinatorial optimizaion with rational objective functions. Mathematics of Operations Research 4, 414–424 (1979)
Wald, J.A., Colbourn, C.J.: Steiner trees, partial 2-trees, and minimum IFI networks. Networks 13, 159–167 (1983)
Zielinski, P.: The computational complexity of the relative robust shortest path problem with interval data. European Journal Operational Research 158, 570–576 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Álvarez-Miranda, E., Candia, A., Chen, X., Hu, X., Li, B. (2010). Efficient Algorithms for the Prize Collecting Steiner Tree Problems with Interval Data. In: Chen, B. (eds) Algorithmic Aspects in Information and Management. AAIM 2010. Lecture Notes in Computer Science, vol 6124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14355-7_3
Download citation
DOI: https://doi.org/10.1007/978-3-642-14355-7_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14354-0
Online ISBN: 978-3-642-14355-7
eBook Packages: Computer ScienceComputer Science (R0)