Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) GALaC
Fighting epidemics with the maximum spectral subgraph
Paul Beaujean

08 March 2019, 14h30
Salle/Bat : 445/PCRI-N
Contact :

Activités de recherche : Théorie des graphes

Résumé :
Recent developments in mathematical epidemiology have identified a relationship between the time to extinction of an epidemic spreading over a network and the spectral radius of the underlying graph i.e. the largest eigenvalue of its adjacency matrix. At the same time, new generation networking technologies such as NFV (network function virtualization) and SDN (software-defined networking) have enabled real-time reconfiguration of network topology.
In this context, we introduce the maximum spectral subgraph problem: given an undirected graph and a threshold value, the task is to find a partial subgraph with the maximum number of edges such that its spectral radius is bounded above by the threshold. Solving this problem would prescribe an inexpensive network topology reconfiguration which guarantees that a malware epidemic would disappear in a short amount of time.
Unfortunately, the maximum spectral subgraph problem is NP-hard which motivates us to study whether it can be approximated in polynomial time. In this talk, we present a simple randomized (log^2 n)-approximation algorithm based on the relaxation and rounding framework using semidefinite programming together with matrix concentration inequalities.

This talk covers joint work with Cristina Bazgan and Eric Gourdin from the paper:
C. Bazgan, P. Beaujean, and E. Gourdin, Relaxation and matrix randomized rounding for the maximum spectral subgraph problem, COCOA 2018

Pour en savoir plus :
Séminaires
Enhancing Asynchronous Iterative Linear Solvers Th
Calcul à haute performance
Tuesday 21 May 2019 - 10h30
Salle : 465 - PCRI-N
Masha Sosonkina .............................................

Simulation of the M13 infection in E.coli
Algorithmique distribuée
Thursday 09 May 2019 - 10h30
Salle : 465 - PCRI-N
Da-Jung Cho .............................................

Economics of Age of Information (AoI) Management:
Réseaux
Friday 03 May 2019 - 14h30
Salle : 445 - PCRI-N
Lingjie Duan .............................................

Expérimentations sur le calcul hautes performances
Combinatoire
Friday 19 April 2019 - 14h30
Salle : 455 - PCRI-N
Florent Hivert .............................................

Asymptotic behaviour of the 3-state cyclic cellula
Thursday 11 April 2019 - 13h30
Salle : 465 - PCRI-N
Benjamin Hellouin de Menibus .............................................