• 综合
  • 标题
  • 关键词
  • 摘要
  • 学者
  • 期刊-刊名
  • 期刊-ISSN
  • 会议名称
搜索

作者:

Sun, Jian (Sun, Jian.) | Sheng, Haiyun (Sheng, Haiyun.) | Sun, Yuefang (Sun, Yuefang.) | DU, Donglei (DU, Donglei.) | Zhang, Xiaoyan (Zhang, Xiaoyan.)

收录:

SCIE

摘要:

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.

关键词:

approximation algorithm combinatorial optimization Prize-collecting Steiner tree stochastic optimization

作者机构:

  • [ 1 ] [Sun, Jian]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 2 ] [Sheng, Haiyun]Nanjing Normal Univ, Sch Math Sci, Nanjing 210023, Jiangsu, Peoples R China
  • [ 3 ] [Zhang, Xiaoyan]Nanjing Normal Univ, Sch Math Sci, Nanjing 210023, Jiangsu, Peoples R China
  • [ 4 ] [Sheng, Haiyun]Nanjing Normal Univ, Inst Math, Nanjing 210023, Jiangsu, Peoples R China
  • [ 5 ] [Zhang, Xiaoyan]Nanjing Normal Univ, Inst Math, Nanjing 210023, Jiangsu, Peoples R China
  • [ 6 ] [Sun, Yuefang]Ningbo Univ, Sch Math & Stat, Ningbo 315211, Zhejiang, Peoples R China
  • [ 7 ] [DU, Donglei]Univ New Brunswick, Fac Management, Fredericton, NB E3B 5A3, Canada

通讯作者信息:

  • [Zhang, Xiaoyan]Nanjing Normal Univ, Sch Math Sci, Nanjing 210023, Jiangsu, Peoples R China;;[Zhang, Xiaoyan]Nanjing Normal Univ, Inst Math, Nanjing 210023, Jiangsu, Peoples R China

查看成果更多字段

相关关键词:

相关文章:

来源 :

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION

ISSN: 1547-5816

年份: 2021

1 . 3 0 0

JCR@2022

ESI高被引阀值:9

被引次数:

WoS核心集被引频次: 0

SCOPUS被引频次:

ESI高被引论文在榜: 0 展开所有

万方被引频次:

中文被引频次:

近30日浏览量: 3

归属院系:

在线人数/总访问数:987/2990291
地址:北京工业大学图书馆(北京市朝阳区平乐园100号 邮编:100124) 联系我们:010-67392185
版权所有:北京工业大学图书馆 站点建设与维护:北京爱琴海乐之技术有限公司