Approximation algorithms for the fault-tolerant facility location problem with penalties

作     者：Ji, Sai Xu, Dachuan Du, Donglei Wu, Chenchen 

作者机构：Beijing Univ Technol Coll Appl Math Dept Informat & Operat Res Beijing Peoples R China Univ New Brunswick Fac Business Adm Fredericton NB Canada Tianjin Univ Technol Coll Sci Tianjin Peoples R China 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2019年第264卷

页      面：62-75页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：National Natural Science Foundation of China [11728104, 11871081, 11531014] Natural Science and Engineering Research Council of Canada Natural Science Foundation of China 

主　　题：Approximation algorithm Fault-tolerant Facility location problem Penalty 

摘      要：We study the fault-tolerant facility location problem with penalties (FTFLPWP). We present an LP-rounding 4-approximation algorithm. Then we apply the randomized rounding technique to improve the approximation to 3.16, which is further improved to 2.408 by the greedy augmentation technique. (C) 2019 Elsevier B.V. All rights reserved.