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

Author:

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

Indexed by:

CPCI-S EI Scopus

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:

Stochastic prize-collecting Steiner tree Combinatorial optimization Approximation algoritorithm

Author Community:

  • [ 1 ] [Sun, Jian]Nanjing Normal Univ, Sch Math Sci, Nanjing 210023, Jiangsu, 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 ] [Sun, Jian]Nanjing Normal Univ, Inst Math, Nanjing 210023, Jiangsu, Peoples R China
  • [ 5 ] [Sheng, Haiyun]Nanjing Normal Univ, Inst Math, Nanjing 210023, Jiangsu, Peoples R China
  • [ 6 ] [Zhang, Xiaoyan]Nanjing Normal Univ, Inst Math, Nanjing 210023, Jiangsu, Peoples R China
  • [ 7 ] [Sun, Jian]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing 100124, Peoples R China
  • [ 8 ] [Sun, Yuefang]Shaoxing Univ, Sch Math Informat, Shaoxing 312000, Zhejiang, Peoples R China

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 :

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:

Online/Total:536/10648454
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.