A location problem on a network with centrally connected service area. (Russian) Zbl 0644.90028

Author summary (translated from the Russian): “We consider a location problem on a network whose matrix of transportation costs satisfies a chain condition. We prove the existence of an optimal solution with centrally connected service areas. We describe an exact algorithm for the solution of the problem for networks that have a cyclic quasiblock structure. We prove estimates for the complexity of the algorithm: O(m \(2n+p)\) operations in the case of pseudotree quasiblocks and O(mn 2) in the case of logarithmic boundedness of the number of enterprises in each quasiblock (n is the number of vertices of the network, m is the number of possible enterprises, p is the number of edges in the network).”


90B05 Inventory, storage, reservoirs
90B10 Deterministic network models in operations research
68Q25 Analysis of algorithms and problem complexity