Combinatorial approximation algorithms for the robust facility location problem with penalties |
| |
| Authors: | Fengmin?Wang Email author" target="_blank">Dachuan?XuEmail author Chenchen?Wu |
| |
| Institution: | 1.Department of Information and Operations Research,Beijing University of Technology,Beijing,People’s Republic of China;2.College of Science,Tianjin University of Technology,Tianjin,People’s Republic of China |
| |
| Abstract: | In this paper, we consider the robust facility location problem with penalties, aiming to serve only a specified fraction of the clients. We formulate this problem as an integer linear program to identify which clients must be served. Based on the corresponding LP relaxation and dual program, we propose a primal–dual (combinatorial) 3-approximation algorithm. Combining the greedy augmentation procedure, we further improve the above approximation ratio to 2. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
