UC Berkeley

Spielman and Teng's nearly linear time algorithm for solving Laplacian systems was a breakthrough in combining techniques from discrete and continuous optimization. In this dissertation we adapt their approach to solve more general flow problems, overcoming long-standing barriers in continuous optimization. As a result we solve longstanding open questions in optimization by presenting nearly-linear time approximation algorithms for the undirected versions of several network flow problems, including \emph{maximum flow}, \emph{optimal transportation}, \emph{maximum concurrent multi-commodity flow}, and \emph{sparsest cut} problems.

Our contributions include two general tools. The first is a scheme for boosting the performance of iterative solvers for continuous optimization problems. These boosters use recursive composition to achieve residual error that decreases exponentially in the number of iterations of the solver.

The second is a technique for designing iterative solvers that bypasses the infamous $\ell_{\infty}$ barrier for strongly convex regularization. Instead we introduce the notion of an area convex regularizer, and show that such regularizers suffice in designing good iterative solvers. Moreover, we show how to design regularizers satisfying this weaker property for the problem of approximately solving $A X \leq B$ over right stochastic $X$, which in turn implies the algorithm for maximum concurrent multi-commodity flow.