Analysis and Complexity of Node-Immunization under Natural Disasters
Conference: DRCN 2017 – Design of Reliable Communication Networks - 13th International Conference
03/08/2017 - 03/10/2017 at München, Deutschland
Proceedings: DRCN 2017 – Design of Reliable Communication Networks
Pages: 8Language: englishTyp: PDF
Personal VDE Members are entitled to a 10% discount on this title
Authors:
Aprile, Manuel (École Polytechnique Fédérale de Lausanne, Discrete Optimization Group, Station 8, 1015 Lausanne, Switzerland)
Castro, Natalia; Robledo, Franco; Romero, Pablo (Facultad de Ingeniería, Universidad de la República, Instituto de Matemática y Estadística, IMERL, Julio Herrera y Reissig 565, Montevideo, Uruguay)
Abstract:
The object under study is natural disaster management via node-immunization subject to budget constraints. The system is modelled by a network, where a single node is exposed to a natural disaster that is immediately propagated through neighbouring nodes. The goal is to choose a node-immunization strategy in order to minimize the disaster. Examples of natural disasters include a fire, an electric shock or pandemics, among others. Our contribution is three-fold. First, the system under risk is modelled by means of a combinatorial optimization problem. Second, the hardness and universal inapproximability to optimality is formally proved. Third, the optimum immunization strategy is found for all acyclic graph, elementary cycles and some bipartite graphs, in strong contrast to the previous negative results.