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

作     者：Arie Tamir 

出 版 物：《SIAM Journal on Discrete Mathematics》 

年 卷 期：1988年第1卷第3期

页      面：377-396页

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：05C35 90C27 68R10 68U05 location theory network center problems dynamic data structures 

摘      要：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.