CSpace
Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data
Alternative TitleRisk Models for the Prize Collecting Steiner Tree Problems with Interval Data
AlvarezMiranda Eduardo1; CandiaVejar Alfredo1; Chen Xujin3; Hu Xiaodong3; Li Bi3
2014
Source PublicationACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES
ISSN0168-9673
Volume30Issue:1Pages:1-26
AbstractGiven a connected graph G = (V, E) with a nonnegative cost on each edge in E, a nonnegative prize at each vertex in V, and a target set V-1 subset of V, the Prize Collecting Steiner Tree (POST) problem is to find a tree T in G interconnecting all vertices of V-1 such that the total cost on edges in T minus the total prize at vertices in T is minimized. The PCST problem appears frequently in practice of operations research. While the problem is NP-hard in general, it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.
Other AbstractGiven a connected graph G=(V,E)with a nonnegative cost on each edge in E,a nonnegative 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 in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost x_e∈c_e~-,c_e~+while taking risk(c_e~+ x_e)/(c_e~+ c_e)of malfunction at e,and vertex v could be asked for giving a prize y_v∈p_v~-,p_v~+for its inclusion in T while taking risk(y_v -p_v~-)/(p_v~+ p_v~-)of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.
KeywordSERIES-PARALLEL GRAPHS SHORTEST-PATH PROBLEM COMPUTATIONAL-COMPLEXITY NETWORK OPTIMIZATION CONSTRAINTS ALGORITHMS FLOWS uncertainty modeling prize collecting Steiner tree interval data series-parallel graphs polynomial-time solvability
Indexed ByCSCD
Language英语
Funding Project[National Natural Science Foundation of China] ; [973 Program of China] ; [Chinese Academy of Sciences] ; [Center for Research and Applications in Plasma Physics and Pulsed Power Technology, PBCT-Chile-ACT 26] ; [Direccion de Programas de Investigacion, Universidad de Talca, Chile]
CSCD IDCSCD:5097895
Citation statistics
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/53487
Collection中国科学院数学与系统科学研究院
Affiliation1.University Talca, Ind Management Dept, Talca, Chile
2.University Bologna, DEI, I-40126 Bologna, Italy
3.中国科学院数学与系统科学研究院
Recommended Citation
GB/T 7714
AlvarezMiranda Eduardo,CandiaVejar Alfredo,Chen Xujin,et al. Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data[J]. ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES,2014,30(1):1-26.
APA AlvarezMiranda Eduardo,CandiaVejar Alfredo,Chen Xujin,Hu Xiaodong,&Li Bi.(2014).Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data.ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES,30(1),1-26.
MLA AlvarezMiranda Eduardo,et al."Risk Models for the Prize Collecting Steiner Tree Problems with Interval Data".ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES 30.1(2014):1-26.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[AlvarezMiranda Eduardo]'s Articles
[CandiaVejar Alfredo]'s Articles
[Chen Xujin]'s Articles
Baidu academic
Similar articles in Baidu academic
[AlvarezMiranda Eduardo]'s Articles
[CandiaVejar Alfredo]'s Articles
[Chen Xujin]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[AlvarezMiranda Eduardo]'s Articles
[CandiaVejar Alfredo]'s Articles
[Chen Xujin]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.