Abstract
In this paper, we consider an interesting variant of the facility location problem called uncapacitated facility location problem with penalties (UFLWP for short) in which each client is either assigned to an opened facility or rejected by paying a penalty. We present a 1.8526-approximation algorithm for the UFLWP problem. Our algorithm first enhances the primal-dual method for the UFLWP problem [3] so that outliers can be recognized more efficiently, and then applies a local search heuristic to further reduce the cost for serving those non-rejected clients.
| Original language | English |
|---|---|
| Pages (from-to) | 644-653 |
| Number of pages | 10 |
| Journal | Lecture Notes in Computer Science |
| Volume | 3595 |
| DOIs | |
| State | Published - 2005 |
| Event | 11th Annual International Conference on Computing and Combinatorics, COCOON 2005 - Kunming, China Duration: Aug 16 2005 → Aug 29 2005 |
Keywords
- Algorithms
- Approximation Algorithms
- Facility Location Problem
- Outliers
Fingerprint
Dive into the research topics of 'An improved approximation algorithm for uncapacitated facility location problem with penalties'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver