Title: Graph Algorithms and Offline Processing
Presented By: Richard Peng, Georgia Institute of Technology

Abstract:
Graphs, which in their simplest forms are vertices connected by edges, are widely used in high scientific computing, machine learning and network science. This talk will use recent progresses on two well studied graph problems, network flows and dynamic matchings, to discuss a general approach for designing provably efficient graph algorithms. This approach revolves around the usage of offline, or batched, processing to combine approximations with iterative procedures that control the approximation errors.

I will start by describing how the study of vertex labeling problems and their duals, network flows, led to a focus on preconditioning with residual graphs. I will then discuss a similar phenomenon in dynamic graph data structures, where large matchings in changing graphs are maintained through batched construction of smaller equivalent graphs. In both of these cases, the algorithms can be viewed as making a natural online path finding scheme as offline as possible through the design of suitable intermediate structures and the control of approximation errors.