×

zbMATH — the first resource for mathematics

A polynomial algorithm for solving the facility location problem on a chain network with identical plant production capacities. (Russian) Zbl 1249.90295
Summary: A facility location problem with uniform capacities on a chain network is considered. Previously, A. A. Ageev has shown that this problem can be solved in \(O(m^5n^2 + m^3n^3)\) time, where \(m\) is the number of facilities and \(n\) is the number of clients. We present a modified algorithm that reduces the time complexity to \(O(m^4 n^2)\).

MSC:
90C35 Programming involving graphs or networks
90B80 Discrete location and assignment
PDF BibTeX XML Cite