| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 436926 | Theoretical Computer Science | 2013 | 9 Pages |
Abstract
We offer the currently best approximation ratio 2.375 for the facility location problem with submodular penalties (FLPSP), improving not only the previous best combinatorial ratio 3, but also the previous best non-combinatorial ratio 2.488. We achieve this improved ratio by combining the primal–dual scheme with the greedy augmentation technique.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
