Approximation Algorithms for the Priority Facility Location Problem with Penalties

作     者：WANG Fengmin XU Dachuan WU Chenchen 

作者机构：College of Applied Sciences Beijing University of Technology College of Science Tianjin University of Technology 

出 版 物：《Journal of Systems Science & Complexity》 (系统科学与复杂性学报(英文版))

年 卷 期：2015年第28卷第5期

页      面：1102-1114页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学] 

基　　金：supported by the National Natural Science Foundation of China under Grant No.11371001 

主　　题：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.