|
|||||
|
|
A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties |
|
| Authors: | Yu Li Donglei Du Naihua Xiu Dachuan Xu |
| Institution: | 1. Department of Mathematics, School of Science, Beijing Jiaotong University, 3 Shangyuancun, Haidian District, Beijing, 100044, P.R. China 2. Faculty of Business Administration, University of New Brunswick, Fredericton, NB, Canada, E3B 5A3 3. Department of Applied Mathematics, Beijing University of Technology, 100 Pingleyuan, Chaoyang District, Beijing, 100124, P.R. China |
| Abstract: | In this paper, we study two variants of the classical facility location problem, namely, the facility location problem with linear penalties (FLPLP) and the facility location problem with submodular penalties (FLPSP), respectively. We give a unified dual-fitting based approximation algorithm for these two problems, yielding approximation ratios 2 and 3 respectively. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |