Attività del Dipartimento
Colloquium di Matematica Laplacian-based Optimization Algorithms Vincenzo Bonifaci 21-11-2018 - 16:00 Aula F, primo piano, edificio Aule - Largo San Leonardo Murialdo,1
A classic approach to network optimization problems involves combinatorial methods and tools from discrete mathematics and graph theory. Over the last decade, however, a new approach has emerged in which combinatorial network problems are reduced to the solution of several linear equation systems of the form Lx = b, where L is the Laplacian matrix of a graph. This approach combines techniques from linear algebra and graph theory, bridging the discrete setting of combinatorial optimization with the numerical setting of scientific computing and convex optimization.
In particular, the development of fast Laplacian solvers, running in time nearly-linear in the number of edges of the associated graph, has enabled a new generation of fast and conceptually simple algorithms for fundamental network problems. We review this "Laplacian paradigm" through some classic examples. We then discuss two of our contributions in this area: a Laplacian-based approach to the shortest path problem --which can also be generalized to linear optimization problems-- and a random-walk based distributed algorithm for the solution of a Laplacian system. |