The facility location problem with general cost functions
Abstract
In this paper, we introduce a generalized version of the facility location problem in which the facility cost is a function of the number of clients assigned to the facility. We focus on the case of concave facility cost functions. We observe that this problem can be reduced to the uncapacitated facility location problem. We analyze a natural greedy algorithm for this problem and show that its approximation factor is at most 1.861. We also consider several generalizations and variants of this problem.Keywords
This publication has 21 references indexed in Scilit:
- Improved Approximation Algorithms for Metric Facility Location Problems2002
- An Improved Approximation Algorithm for the Metric Uncapacitated Facility Location Problem2002
- A Greedy Facility Location Algorithm Analyzed Using Dual Fitting2001
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxationJournal of the ACM, 2001
- Analysis of a Local Search Heuristic for Facility Location ProblemsJournal of Algorithms, 2000
- Improved Approximation Algorithms for Capacitated Facility Location Problems1999
- Greedy Strikes Back: Improved Facility Location AlgorithmsJournal of Algorithms, 1999
- Improved Approximation Algorithms for Uncapacitated Facility Location1998
- An improved approximation ratio for the minimum latency problemMathematical Programming, 1998
- New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalitiesIEEE Transactions on Information Theory, 1977