Improved Exact Algorithm for the Capacitated Facility Location Problem on a Line Graph
Authors:
- 1 August 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 53-57
Abstract
In the Capacitated Facility Location Problem (CFLP) the goal is to optimally place facilities at the vertices of a transportation network graph in order to minimize the total facility opening and transportation costs while considering additional restrictions on the facility capacities. The general problem is NP-hard. In this paper we study a special case of the CFLP, where the input transportation network graph is a line graph. We show how to improve the running-time of the best known pseudopolynomial-time algorithm for the CFLP on a line graph from [Mirchandani et al., 1996] by one order.Keywords
This publication has 8 references indexed in Scilit:
- Location Science2015
- LP-based approximation algorithms for capacitated facility locationMathematical Programming, 2010
- FLoSS: Facility location for subspace segmentation2009
- AN MDL METHOD FOR FINDING HAPLOTYPE BLOCKS AND FOR ESTIMATING THE STRENGTH OF HAPLOTYPE BLOCK BOUNDARIES2002
- Capacitated Location Problems on a LineTransportation Science, 1996
- Improved complexity bounds for location problems on the real lineOperations Research Letters, 1991
- The concave least-weight subsequence problem revisitedJournal of Algorithms, 1988
- Geometric applications of a matrix-searching algorithmAlgorithmica, 1987