Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures
Author:
- Arie TamirATArie Tamir
- 1 August 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 1 (3) , 377-396
Abstract
Several center location problems on general networks and even on tree networks are nonconvex. Known solution procedures are based on decomposing the problem into subproblems, finding each one of the local solutions independently, and then selecting among them the best solution. The purpose of this paper is to demonstrate that for some location models, it is possible to take advantage and use information that is common to certain subproblems in order to obtain better complexity bounds. The main tool implemented is a dynamic data structure that is used to maintain the objective (dynamically) as we move from one subproblem to the next. This study focuses on (nonconvex) obnoxious center location problems on trees, and on the classical p-center problem on general networks. In both cases better complexity bounds are derived.Keywords
This publication has 22 references indexed in Scilit:
- Fast Algorithms for Shortest Paths in Planar Graphs, with ApplicationsSIAM Journal on Computing, 1987
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- On k-Hulls and Related ProblemsSIAM Journal on Computing, 1987
- Slowing down sorting networks to obtain faster sorting algorithmsJournal of the ACM, 1987
- Constructing Belts in Two-Dimensional Arrangements with ApplicationsSIAM Journal on Computing, 1986
- Some dynamic computational geometry problemsComputers & Mathematics with Applications, 1985
- Location of Multiple Obnoxious FacilitiesTransportation Science, 1985
- Linear Time Algorithms for Two- and Three-Variable Linear ProgramsSIAM Journal on Computing, 1984
- Convex Location Problems on Tree NetworksOperations Research, 1976
- Optimal Center Location in Simple NetworksTransportation Science, 1971