收录:
摘要:
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 programming to identify which clients must be served. Based on the corresponding LP relaxation and dual program, we propose a primaldual 3-approximation algorithm. Combining the greedy augmentation procedure, we further improve the above approximation ratio to 2.
关键词:
通讯作者信息: