Loading...
Please wait, while we are loading the content...
Similar Documents
Improved approximation algorithms for capacitated facility location problems (1999).
| Content Provider | CiteSeerX |
|---|---|
| Author | Chudak, Fabián A. Williamson, David P. |
| Abstract | In a recent surprising result, Korupolu, Plaxton, and Rajaraman [10, 11] showed that a simple local search heuristic for the capacitated facility location problem (CFLP) in which the service costs obey the triangle inequality produces a solution in polynomial time which is within a factor of 8 + ffl of the value of an optimal solution. By simplifying their analysis, we are able to show that the same heuristic produces solution which are within a factor of 6(1 + ffl) of the value of an optimal solution. Our simplified analysis uses the supermodularity of the cost function of the problem and the integrality of the transshipment polyhedron. Additionally, we consider the variant of the CFLP in which one may open multiple copies of any facility. Using ideas from the analysis of the local search heuristic, we show how to turn any ff-approximation algorithm for this variant into one which, at an additional cost of twice the optimal of the standard CFLP, opens at most one additional copy of an... |
| File Format | |
| Publisher Date | 1999-01-01 |
| Access Restriction | Open |
| Subject Keyword | Capacitated Facility Location Problem Approximation Algorithm Optimal Solution Simple Local Search Heuristic Ff-approximation Algorithm Polynomial Time Triangle Inequality Service Cost Standard Cflp Additional Cost Local Search Multiple Copy Cost Function Simplified Analysis Additional Copy Heuristic Produce Solution Transshipment Polyhedron Recent Surprising Result |
| Content Type | Text |
