收录:
摘要:
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.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION
ISSN: 1547-5816
年份: 2021
1 . 3 0 0
JCR@2022
ESI高被引阀值:87
JCR分区:3
归属院系: