• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

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

Indexed by:

EI Scopus SCIE

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:

combinatorial optimization Prize-collecting Steiner tree stochastic optimization approximation algorithm

Author Community:

  • [ 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

Reprint Author's Address:

  • [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

Show more details

Related Keywords:

Related Article:

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:

Online/Total:734/10649740
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.