Efficient Algorithms for the Prize Collecting Steiner Tree Problems with Interval Data

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\'\\subseteq 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ın[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ın [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.
Type de document :
Communication dans un congrès
Proceedings of the 6th International Conference on Algorithmic Aspects in Information and Management (AAIM), 2010, Weihai, China, Springer, 6124, pp.13-24, 2010, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/hal-00794824
Contributeur : Alain Monteil <>
Soumis le : mardi 26 février 2013 - 15:37:41
Dernière modification le : mardi 26 février 2013 - 16:49:51

Identifiants

  • HAL Id : hal-00794824, version 1

Citation

E. Alvarez-Miranda, A. Candia, X. Chen, X. Hu, B. Li. Efficient Algorithms for the Prize Collecting Steiner Tree Problems with Interval Data. Proceedings of the 6th International Conference on Algorithmic Aspects in Information and Management (AAIM), 2010, Weihai, China, Springer, 6124, pp.13-24, 2010, Lecture Notes in Computer Science. 〈hal-00794824〉

Partager

Métriques

Consultations de la notice

18