Optimization on Graphs

Rasmus Kyng (Theory of Computation, Harvard University)

Full title: How to Solve Problems on Graphs Using Linear Equations, and How to Solve Linear Equations Using Graphs

Graphs give us a simple model of a network. Based on this model, we can ask many interesting questions. For example, we can analyze social networks using clustering and regression. In transportation networks, we want to understand and plan flows of traffic, goods, or data. Answering our questions often boils down to solving an optimization problem on a graph. Second order methods are a powerful tool in optimization, but they require solving linear equations, which can be prohibitively expensive. But when the optimization problem comes from a graph, this adds structure to the linear equations. We can leverage this structure to solve the equations quickly, making second order methods tractable. This insight has been one of the drivers of a major line of research in graph algorithms, known as the Laplacian Paradigm. In this talk, we will see how graph-structured optimization problems give rise to nice linear equations. We will also see how thinking about these linear equations in terms of graphs will let us develop very efficient algorithms for solving them. Finally, we will explore ideas that have recently played a role in making solvers for these linear equations more practical.

License: CC BY-NC-SA 4.0
- https://creativecommons.org/licenses/...