E±cient Algorithms for the Prize Collecting Steiner Tree Problems with Interval Data - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

E±cient Algorithms for the Prize Collecting Steiner Tree Problems with Interval Data

Eduardo Alvarez-Miranda
  • Fonction : Auteur
A. Candia
  • Fonction : Auteur
Xujin Chen
  • Fonction : Auteur
Xiaodong Hu
  • Fonction : Auteur
Bi Li
  • Fonction : Auteur
  • PersonId : 881612

Résumé

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\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.

Dates et versions

inria-00532630 , version 1 (04-11-2010)

Identifiants

Citer

Eduardo Alvarez-Miranda, A. Candia, Xujin Chen, Xiaodong Hu, Bi Li. E±cient Algorithms for the Prize Collecting Steiner Tree Problems with Interval Data. Algorithmic Aspects in Information and Management, Jul 2010, Weihai, China. ⟨10.1007/978-3-642-14355-7⟩. ⟨inria-00532630⟩
27 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More