An Approximation Algorithm for the Facility Location Problem with Lexicographic Minimax Objective
Open Access
- 17 June 2014
- journal article
- research article
- Published by Hindawi Limited in Journal of Applied Mathematics
- Vol. 2014, 1-12
Abstract
We present a new approximation algorithm to the discrete facility location problem providing solutions that are close to the lexicographic minimax optimum. The lexicographic minimax optimum is a concept that allows to find equitable location of facilities serving a large number of customers. The algorithm is independent of general purpose solvers and instead uses algorithms originally designed to solve thep-median problem. By numerical experiments, we demonstrate that our algorithm allows increasing the size of solvable problems and provides high-quality solutions. The algorithm found an optimal solution for all tested instances where we could compare the results with the exact algorithm.Keywords
This publication has 33 references indexed in Scilit:
- A Multiperiod School Location Planning Approach with Free School ChoiceEnvironment and Planning A: Economy and Space, 2009
- Inequality measures and equitable locationsAnnals of Operations Research, 2007
- The gravity p-median modelEuropean Journal of Operational Research, 2007
- On the distribution approach to location problemsComputers & Industrial Engineering, 1999
- Geometric methods to solve max-ordering location problemsDiscrete Applied Mathematics, 1999
- Rate control for communication networks: shadow prices, proportional fairness and stabilityJournal of the Operational Research Society, 1998
- On the lexicographic minimax approach to location problemsEuropean Journal of Operational Research, 1997
- OR-Library: Distributing Test Problems by Electronic MailJournal of the Operational Research Society, 1990
- A good algorithm for lexicographically optimal flows in multi-terminal networksBulletin of the American Mathematical Society, 1977
- A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock ProblemCanadian Journal of Mathematics, 1957