Article ID: | iaor1988929 |
Country: | United States |
Volume: | 1 |
Issue: | 3 |
Start Page Number: | 377 |
End Page Number: | 396 |
Publication Date: | Aug 1988 |
Journal: | SIAM Journal On Discrete Mathematics |
Authors: | Tamir Arie |
Keywords: | combinatorial analysis, networks |
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