|
Diskretnyi Analiz i Issledovanie Operatsii, 2009, Volume 16, Issue 5, Pages 3–18
(Mi da582)
|
|
|
|
This article is cited in 5 scientific papers (total in 5 papers)
Polynomial algorithm for the path facility location problem with uniform capacities
A. A. Ageev, E. Kh. Gimadi, A. A. Kurochkin S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
Abstract:
The Facility Location Problem with uniform capacities on path graphs is considered. Earlier it was shown by Ageev that this problem can be solved in $O(m^3n^3+m^5n^2)$ time, where $m$ is the number of facilities and $n$ is the number of clients. In the paper the modified algorithm is presented that has reduced infinitesimal order for the time complexity $O(m^4n^2)$. Ill. 9, bibl. 24.
Keywords:
facility location, uniform capacities, path graphs, polynomial-time algorithm.
Received: 25.06.2009
Citation:
A. A. Ageev, E. Kh. Gimadi, A. A. Kurochkin, “Polynomial algorithm for the path facility location problem with uniform capacities”, Diskretn. Anal. Issled. Oper., 16:5 (2009), 3–18
Linking options:
https://www.mathnet.ru/eng/da582 https://www.mathnet.ru/eng/da/v16/i5/p3
|
Statistics & downloads: |
Abstract page: | 592 | Full-text PDF : | 156 | References: | 55 | First page: | 8 |
|