Improved Complexity Bounds for Center Location Problems on Networks by Using Dynamic Data Structures

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.