Discovering independent sets of maximum size in large sparse random graphs.

Resumen:  Finding an independent set of maximum size is a NP-hard task on fixed graphs, and can take an exponentially long-time for optimal stochastic algorithms like Glauber dynamics with high activation rates. However, simple algorithms of polynomial complexity seem to perform well in some instances. We  studied the large graph characteristics of two simple algorithms in terms of functional law of large numbers and large deviations. We are especially interested in characterizing a phase transition on the “graph landscape”, implying that some simple algorithms are asympotically optimal for low connectivity and suboptimal for high connectivity. Based on a joint works with David García-Zelada, Alon Nishry and Aron Wennman.

 

Date: May 26, 2021 at 16:15:00 h
Venue: Modalidad Vía Online.
Speaker: Matthieu Jonckheere
Affiliation: Universidad de Buenos Aires – CONICET, Argentina
Coordinator: Avelio Sepúlveda
More info at:
Event website
Abstract:
PDF

Posted on May 24, 2021 in Seminario Probabilidades CMM, Seminars