Improved complexity bounds for center location problems on networks by using dynamic data structures

Improved complexity bounds for center location problems on networks by using dynamic data structures

0.00 Avg rating0 Votes
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:
Keywords: combinatorial analysis, networks
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.

Reviews

Required fields are marked *. Your email address will not be published.