Title: Approximation Algorithm for Stochastic Set Cover Problem
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 $$2\eta $$ -approximation algorithm for the stochastic set cover problem with submodular penalties (4-approximation algorithm for the stochastic vertex cover problem with submodular penalties when $$\eta =2$$ ), where $$\eta $$ is the maximum frequency of the element in the family of subsets.
Publication Year: 2020
Publication Date: 2020-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot