Seminário do Departamento de Informática e do LISP, no dia 28/1 (quinta feira) às 14:30, na sala 134 do CLV.

Title: Network Interdiction problem and Sustainable Networks

Bio:

Jean-Francois Baffier graduated (Master) from the University of Paris XI in 2011 and got his Ph.D. from the University of Tokyo in 2015. His main research topics cover modeling of failures and routing in Networks. Other research topics involve Game analysis and AI for Games (in particular Starcraft), but also Local Search algorithms (HPC) and limited memory algorithms.

He is currently a member of the JST-ERATO Kawarabayashi project on Large Graphs (Big Data) in Tokyo/Sendai, JAPAN.

Abstract:

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.