Indexed by:
Abstract:
Steiner tree problem is a typical NP-hard problem, which has vast application background and has been an active research topic in recent years. Stochastic optimization problem is an important branch in the field of optimiza-tion. Compared with deterministic optimization problem, it is an optimization problem with random factors, and requires the use of tools such as probability and statistics, stochastic process and stochastic analysis. In this paper, we study a two-stage finite-scenario stochastic prize-collecting Steiner tree prob-lem, where the goal is to minimize the sum of the first stage cost, the expected second stage cost and the expected penalty cost. Our main contribution is to present a primal-dual 3-approximation algorithm for this problem.
Keyword:
Reprint Author's Address:
Email:
Source :
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION
ISSN: 1547-5816
Year: 2021
1 . 3 0 0
JCR@2022
ESI Discipline: ENGINEERING;
ESI HC Threshold:87
JCR Journal Grade:3
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: 1
Affiliated Colleges: