The facility location problem with general cost functions
Given a finite set of clients and a finite set of possible facility sites, the concave facility location problem considered in this paper is to find an assignment of all clients to facility sites such that the sum of connection costs and facility costs is minimized. It is assumed that the connection costs are symmetric and satisfy the triangle inequality, and that the facility costs are given by concave functions of the number of clients assigned to the respective facility. It is first noted that the concave facility location problem can be reduced to the capacitated facility location problem for which a 1.52-approximation algorithm with a time complexity of \(O(n^6)\) was given by \textit{M. Mahdian, Y. Ye} and \textit{J. Zhang} [Lect. Notes Comput. sci. 2462, 229-242 (2002; Zbl 1013.90115)] and \textit{M. Mahdian, E. Markakis, A. Saberi} and \textit{V. Vazirani} [Lect. Notes Comput. Sci. 2129, 127-137 (200; Zbl 0998.68701)]. Then a greedy-type 1.861-approximation algorithm with an improved running time of at most \(O(n^3 \log n)\) is presented. The algorithm can be viewed as a natural generalization of an earlier algorithm by Mahdian, Markakis, Saberi and Vazirani (2001). This also extends to the derivation of the approximation factor of 1.861 which uses techniques of dual-fitting and factor-revealing LPs.
- A greedy facility location algorithm analyzed using dual fitting
- A new greedy approach for facility location problems
- An improved approximation algorithm for the metric uncapacitated facility location problem
- Approximation algorithms for facility location problems
- scientific article; zbMATH DE number 1305496 (Why is no real title available?)
- scientific article; zbMATH DE number 1118889 (Why is no real title available?)
- Local search heuristic for k-median and facility location problems
- An effective linear approximation method for separable programming problems
- A 6.55 factor primal-dual approximation algorithm for the connected facility location problem
- A multi-objective facility location problem in the presence of variable gradual coverage performance and cooperative cover
- Polyhedral results for a class of cardinality constrained submodular minimization problems
- A computational study of a nonlinear minsum facility location problem
- Preference elicitation and robust winner determination for single- and multi-winner social choice
- Clique partitioning with value-monotone submodular cost
- Improved local search for universal facility location
- Capacitated refueling station location problem with traffic deviations over multiple time periods
- A new approximation algorithm for the k-facility location problem
- A cross-monotonic cost-sharing scheme for the concave facility location game
- An approximation algorithm for the \(k\)-median warehouse-retailer network design problem
- From stars to comets: improved local search for universal facility location
- An approximation algorithm for a facility location problem with stochastic demands and inventories
- A Lagrangian heuristic for concave cost facility location problems: the plant location and technology acquisition problem
- Discretized formulations for capacitated location problems with modular distribution costs
- Location and two-echelon inventory network design with economies and diseconomies of scale in facility operating costs
- Combinatorial approximation algorithms for the robust facility location problem with penalties
- The load-distance balancing problem
- Integrating facility location and production planning decisions
- On a facility location problem with applications to tele-diagnostic
- Decomposition algorithms for data placement problem based on Lagrangian relaxation and randomized rounding
- A branch-and-price algorithm for facility location with general facility cost functions
- Data-driven robust resource allocation with monotonic cost functions
- Competitive Cost Sharing with Economies of Scale
- Competitive cost sharing with economies of scale
- Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints
- Mind the gap: edge facility location problems in theory and practice
- Modeling and solving an economies‐of‐scale service system design problem
- A continuation approach for the capacitated multi-facility weber problem based on nonlinear SOCP reformulation
- Entrepreneurship facility-activation games
- Fault-tolerant concave facility location problem with uniform requirements
- The intersection of location-allocation, partitional clustering and model-based clustering techniques -- a review
- Approximation algorithms for facility location problems with a special class of subadditive cost functions
This page was built for publication: The facility location problem with general cost functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4422623)