Improved approximation of the general soft-capacitated facility location problem
- 1 January 2007
- journal article
- research article
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 41 (1) , 83-93
Abstract
The soft-capacitated facility location problem, where each facility is composed of a variable number of fixed-capacity production units, has been recently studied in several papers, especially in the metric case. In this paper, we only consider the general problem where connection costs do not systematically satisfy the triangle inequality property. We show that an adaptation of the set covering greedy heuristic, where the subproblem is approximately solved by a fully polynomial-time approximation scheme based on cost scaling and dynamic programming, achieves a logaritmic approximation ratio of (1 + ε)H(n) for the problem, where n is the number of customers to be served and H is the harmonic series. This improves the previous bound of 2H(n) for this problem.Keywords
All Related Versions
This publication has 17 references indexed in Scilit:
- Greedy facility location algorithms analyzed using dual fitting with factor-revealing LPJournal of the ACM, 2003
- Approximation algorithms for fractional knapsack problemsOperations Research Letters, 2002
- Master-Slave Strategy and Polynomial ApproximationComputational Optimization and Applications, 2000
- Improved Approximation Algorithms for Capacitated Facility Location Problems1999
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Approximation Schemes for the Restricted Shortest Path ProblemMathematics of Operations Research, 1992
- Heuristics for the fixed cost median problemMathematical Programming, 1982
- Fast Approximation Algorithms for Knapsack ProblemsMathematics of Operations Research, 1979
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979
- Fast Approximation Algorithms for the Knapsack and Sum of Subset ProblemsJournal of the ACM, 1975