Indexed by:
Abstract:
Steiner tree problem is a typical NP-hard problems in combinatorial optimization, which has comprehensive application background and is a hot topic in recent years. In this paper, we study the stochastic prize-collecting Steiner tree problem. Before the actual requirements materialize, we can choose (purchase) some edges in the first stage. When actual requirements are revealed, drawn from a prespecified probability distribution, then there are more edges may be chosen (purchased) for the actual requirements. The goal is to minimize the sum of the first stage cost, the expected second stage cost and the expected penalty cost. We propose a primal-dual 3-approximation algorithm for the stochastic prize-collecting Steiner tree problem.
Keyword:
Reprint Author's Address:
Email:
Source :
ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, AAIM 2019
ISSN: 0302-9743
Year: 2019
Volume: 11640
Page: 261-271
Language: English
Cited Count:
WoS CC Cited Count: 0
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 3
Affiliated Colleges: