Graph algorithms through the lens of continuous optimization
Adrian Vladu
IRIF, Université de Paris
https://www.adrianvladu.org/
Date(s) : 03/07/2020 iCal
14h00 - 15h00
Recent years have witnessed a surge in the development of fast graph algorithms based on continuous optimization primitives. Classically, graph algorithms have relied on purely combinatorial techniques. However, new ideas stemming from Scientific Computing and Machine Learning set forth an emerging theme of algorithm design via continuous optimization. I will provide a tour through some of the techniques that underlie this theme, and show how they can be used to obtain fast algorithms for solving a range of fundamental problems such as: maximum flow, minimum cost flow, or optimal transport with entropic regularization.
This talk is based on https://arxiv.org/pdf/1902.06391.pdf, https://arxiv.org/pdf/2003.04863.pdf, and https://arxiv.org/pdf/1704.02310.pdf, but will be kept self-contained, and will assume no prior background in optimization.
This seminar is organized by LIS, pole Calcul. Link of the visio: https://bbb.lsis.org/b/nat-ka2-j76.
Catégories
