On Some Efficiently Solvable Classes of the Network Facility Location Problem with Constraints on the Capacities of Communication Lines
- 26 July 2021
- journal article
- research article
- Published by Pleiades Publishing Ltd in Proceedings of the Steklov Institute of Mathematics
- Vol. 313 (S1) , S58-S72
Abstract
We study the network facility location problem with constraints on the capacities of communication lines, called Restricted Facility Location Problem (RFLP). It is required to locate facilities at the vertices of a given network graph so as to simultaneously satisfy at minimum cost the demands of customers located at the vertices of the graph. We consider two statements of the problem: the multiple allocation RFLP, where the demand of a customer can be satisfied jointly by several facilities, and the single allocation RFLP, where the demand of a customer must be entirely satisfied by a single facility. We show that the single allocation RFLP is NP-hard even if the network is a simple path and strongly NP-hard if the network is a tree. The multiple allocation RFLP is weakly NP-hard on trees. For this problem, we propose a pseudopolynomial-time algorithm for the case where the network graph has constant treewidth and a linear-time algorithm for the case where the network is a simple path.Keywords
This publication has 20 references indexed in Scilit:
- Simultaneous source locationACM Transactions on Algorithms, 2009
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problemsJournal of Computer and System Sciences, 2003
- Locating Sources to Meet Flow Demands in Undirected NetworksJournal of Algorithms, 2002
- A partial k-arboretum of graphs with bounded treewidthTheoretical Computer Science, 1998
- Treewidth: Algorithmic techniques and results1997
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small TreewidthSIAM Journal on Computing, 1996
- On some optimization problems on k-trees and partial k-treesDiscrete Applied Mathematics, 1994
- Improved complexity bounds for location problems on the real lineOperations Research Letters, 1991
- The concave least-weight subsequence problem revisitedJournal of Algorithms, 1988
- Graph minors. II. Algorithmic aspects of tree-widthJournal of Algorithms, 1986