Abstract: In this paper, we consider the facility location problem with submodular penalties and stochastic demands. The objective is to open a subset of facilities,  to connect a subset of clients to open facilities, and  to penalize the remaining  clients such that the total cost of opening cost, connection cost, inventory cost, handling cost and penalty cost is minimized. Based on the special structure of the problem, we propose a primal-dual 3-approximation algorithm. In the algorithm, we construct a dual feasible solution in the first step followed by constructing the corresponding  primal integer feasible solution in the second step. This  primal integer feasible solution indicates the final opening facility set and penalty client set. We prove that the proposed algorithm can be implemented in polynomial time and the cost of the incurred primal integer feasible solution is no more than 3 times of the optimal value.

Key words: submodular penalties, stochastic demands, approximation algorithm, primal-dual algorithm