Approximation Algorithms for the Priority Facility Location Problem with Penalties

作者：Wang Fengmin; Xu Dachuan^*; Wu Chenchen

来源：Journal of Systems Science and Complexity, 2015, 28(5): 1102-1114.

DOI：10.1007/s11424-014-2157-2

• Approximation algorithm
• facility location problem
• greedy augmentation
• primal-dual

This paper considers the priority facility location problem with penalties. The authors develop a primal-dual 3-approximation algorithm for this problem. Combining with the greedy augmentation procedure, the authors further improve the previous ratio 3 to 1.8526.

• 出版日期2015-10
• 单位北京工业大学; 天津理工大学