AN APPROXIMATION ALGORITHM FOR THE k-LEVEL FACILITY LOCATION PROBLEM WITH SUBMODULAR PENALTIES

作者：Li Gaidi; Wang Zhen; Xu Dachuan^*

来源：Journal of Industrial and Management Optimization, 2012, 8(3): 521-529.

DOI：10.3934/jimo.2012.8.521

• Facility location
• approximation algorithm
• combinatorial algorithm
• primal-dual
• submodular

In this paper, we consider the k-level facility location problem with submodular penalties (k-FLPSP). We propose a primal-dual 6-approximation (combinatorial) algorithm for the k-FLPSP.

• 出版日期2012-8
• 单位北京工业大学