革新知能統合研究センター

Speaker: Jean-françois Baffier, JSPS Post-Doctoral Fellow, Tokyo Institute of Technology

Title: Exact and approximated algorithms for Network Interdiction

Abstract:
Within the last decades, new methods of transmitting information have resulted in the most remarkable changes of modern society. The apparition of many communication networks and devices such as the Internet and mobile phones has not only increased people interactions, but for the first time we have the opportunity to analyze the complex behavior of human societies.

The networks supporting those new means of communication are referred as large-scale networks. They currently support billions of users or terminals and will soon reach 10 billion. Various kind of those networks are used everyday by industrial and academician, but also in everyday life. Whether it be for the road network, water supplies, or telecom, 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 problems 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.
Base of those results are available through the following journal article: https://doi.org/10.1016/j.disopt.2016.05.002