Static and dynamic source locations in undirected networks

作     者：Turner, Lara Gross, Dwi Poetranto Hamacher, Horst W. Krumke, Sven O. 

作者机构：Univ Kaiserslautern Dept Math D-67653 Kaiserslautern Germany INFORM GmbH D-52076 Aachen Germany 

出 版 物：《TOP》 (TOP：西班牙统计学与运筹学学会杂志)

年 卷 期：2015年第23卷第3期

页      面：619-646页

核心收录：

学科分类：0202[经济学-应用经济学] 02[经济学] 020208[经济学-统计学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 0714[理学-统计学（可授理学、经济学学位）] 

基　　金：European Union New Zealand Government as part of the OptALI project Federal Ministry of Education and Research (BMBF), Germany [13N12229, 13N12826, 13N13198] 

主　　题：Source location problem Single cover problem Matroid (Dual) greedy algorithm (Minimal) deficient set Plural cover problem Tree network Linear algorithm Pseudo-polynomial algorithm Fully polynomial-time approximation scheme Dynamic flow NP-hardness 

摘      要：Results from source location in the form of single cover problems in static networks are reviewed and extended by new results for the most general problem with arbitrary demands and costs. The matroidal structure of the single covers is established and used in a new and simple validity proof of the dual greedy algorithm for static single cover problems. Moreover, a primal greedy algorithm is derived which uses a new procedure to find the collection of all minimal deficient sets. For static plural cover problems on trees two linear-time algorithms to solve simultaneous and non-simultaneous problems with uniform costs are presented;for the simultaneous scenario with non-uniform costs, a pseudo-polynomial algorithm is proposed which can be turned into a fully polynomial-time approximation scheme. In contrast to its static counterpart, the single cover problem in dynamic, i.e., time-varying networks is shown to be strongly NP-hard. For special cases of the network topology polynomial algorithms are presented.