Network Interdiction problem and Sustainable Networks

Jean-Francois Baffier

University of Tokyo


Various kind of networks are used everyday by industrials and academician, but also in everyday life. Whether it be for the road network, water supplies, or telecoms, all share a common goal : sending data or matter between different nodes. Those exchanges can be modeled as flow sent between a source (or sources) and a sink (or sinks). Then a classical approach is to optimize the amount of flow. There is a natural interest in theory and in practice to study the robustness and sustainability of such a flow. The Network Interdiction Problem and its variants can be applied directly to evaluate the efficiency of a flow in case of attacks or failures. Unfortunately, the problem from this family are all NP-hard. In our work, we design a set of exact and approximate algorithms that we evaluate on several kind of networks. The fundamental nature of those algorithms allows us to optimize the cost to establish or of a new network and/or reduce the upkeep of an existing structure while guaranteeing the efficiency of the flows based on the scale of possible attacks. The results on those resilient flows are similar to the classical case, providing a large range of applications.

Bio: Jean-Francois Baffier graduated Master course at University Paris XI in 2011 and got Ph.D. from the University of Tokyo in 2015. His main research topic covers modeling of failures and routing in Networks. Other research topics involve Game analysis and AI for Games (in particular Starcraft), but also Local Search algorithm (HPC) and limited memory algorithms. He is currently member of the NII (National Institute for Informatics) - JST-ERATO Kawarabayashi Large Graph Project, University of Tokyo.

Tuesday, January 26 2016