Approximation Algorithm for Stochastic Set Cover Problem - Details

Author：

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

Indexed by：

EI Scopus

Abstract：

Cover　problem　is　a　typical　NP-hard　problem,　which　has　comprehensive　application　background　and　is　a　hot　topic　in　recent　years.　In　this　paper,　we　study　two　stage,　finite　scenarios　stochastic　versions　of　set　cover　problem　with　submodular　penalties　which　is　the　generalization　of　the　stochastic　vertex　cover　problem　with　submodular　penalties.　The　goal　is　to　minimize　the　sum　of　the　first　stage　cost,　the　expected　second　stage　cost　and　the　expected　penalty　cost.　By　doing　some　research　on　the　structural　properties　of　submodular　function,　we　present　a　primal-dual　(Formula　Presented)-approximation　algorithm　for　the　stochastic　set　cover　problem　with　submodular　penalties　(4-approximation　algorithm　for　the　stochastic　vertex　cover　problem　with　submodular　penalties　when　(Formula　Presented)),　where　(Formula　Presented)　is　the　maximum　frequency　of　the　element　in　the　family　of　subsets.　©　2020,　Springer　Nature　Switzerland　AG.

Keyword：

Approximation algorithms NP-hard Stochastic systems

Author Community：

[ 1 ] [Sheng, Haiyun]School of Mathematical Science and Institute of Mathematics, Nanjing Normal University, Nanjing; Jiangsu; 210023, China
[ 2 ] [Du, Donglei]Faculty of Management, University of New Brunswick, Fredericton; NB; E3B 5A3, Canada
[ 3 ] [Sun, Yuefang]School of Mathematical Information, Shaoxing University, Shaoxing; Zhejiang; 312000, China
[ 4 ] [Sun, Jian]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
[ 5 ] [Zhang, Xiaoyan]School of Mathematical Science and Institute of Mathematics, Nanjing Normal University, Nanjing; Jiangsu; 210023, China