带次模惩罚和随机需求的设施选址问题

Facility location problem with submodular penalties and stochastic demands

考虑带次模惩罚和随机需求的设施选址问题,目的是开设设施集合的一个子集,把客户连接到开设的设施上并对没有连接的客户进行惩罚,使得开设费用、连接费用、库存费用、管理费用和惩罚费用之和达到最小.根据该问题的特殊结构,给出原始对偶3-近似算法.在算法的第一步,构造了一组对偶可行解;在第二步中构造了对应的一组原始整数可行解,这组原始整数可行解给出了最后开设的设施集合和被惩罚的客户集合.最后,证明了算法在多项式时间内可以完成,并且算法所给的整数解不会超过最优解的3倍.

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.