Big Data Analytics 2013

Big Data Analytics 2013

Invited talk

Cuts, Trees, and Electrical Flows

Aleksander Madry, EPFL

We discuss some of the recent developments in algorithmic graph theory that are relevant in the context of dealing with massive graphs.

In particular, we present a general framework for obtaining close-to-linear-time approximation algorithms for cut problems in undirected graph. We also introduce the electrical flow paradigm that played key role in some of the recent progress on designing fast algorithms for fundamental flow problems.