Ageev, A. A.; Gimadi, Eh. Kh.; Kurochkin, A. A. A polynomial algorithm for solving the facility location problem on a chain network with identical plant production capacities. (Russian) Zbl 1249.90295 Diskretn. Anal. Issled. Oper. 16, No. 5, 3-18 (2009). 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)\). Cited in 3 Documents MSC: 90C35 Programming involving graphs or networks 90B80 Discrete location and assignment Keywords:facility location; uniform capacities; path graph; polynomial-time algorithm PDF BibTeX XML Cite \textit{A. A. Ageev} et al., Diskretn. Anal. Issled. Oper. 16, No. 5, 3--18 (2009; Zbl 1249.90295)