Approximation Algorithms For Some Stochastic Problems Of Combinatorial Optimization

Both cover problem and steiner tree problem are all typical NP-hard prob-lems,which have comprehensive application background and are hot topics in recent years.In this thesis,we study two stage,finite scenarios stochastic ver-sions of several combinatorial optimization problems including the stochastic set cover problem with submodular penalties(the stochastic vertex cover prob-lem with submodular penalties is a special case of it)and the stochastic prize-collecting steiner tree problem.Before the actual requirements materialize,we can choose(purchase)some sets or edges in the first stage.When actual re-quirements are revealed,drawn from a prespecified probability distribution,then there are more sets or edges may be chosen(purchased)for the actual require-ments,but each client in each scenario is not necessarily required to be served by a purchased set or edge,and the set of unserved clients incurs(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?-approximation algorithm for the stochastic set cover problem with submodular penalties(4-approximation algorithm for the stochastic vertex cover problem with submodular penalties when ?= 2),where ? is the maximum frequen-cy of the element in the family of subsets.We also propose a primal-dual 3-approximation algorithm for the stochastic prize-collecting steiner tree problem.