An electrical flow on a graph is a special type of flow which corresponds to the physical interpretation of an electrical current induced on a network of conductors when an electrical circuit is set up. Electrical flow has interesting algebraic properties and is a useful algorithmic primitive in modern algorithm design and is used in recent breakthroughs in long-standing problems such as solving the approximate maximum flow problem [CKM⁺11].

The "minimum energy, demand satisfying, electrical flow" problem is to find an electrical flow of minimum energy that satisfies the demand on the vertices. This problem can be solved using Laplacian Solvers in nearly linear time and many vertex potential based solvers such as [KMP11, CKM⁺14] have been developed. In [KOSZ13], a "cycle toggling" electrical solver was introduced. The cycle flow solver operates in the dual space of the vertex potential solvers and it is considered a simpler algorithm. Despite having a competitive asymptotic running time, the cycle toggling solver was shown to have poorer performance experimentally when compared to traditional optimization methods [DGM⁺16].

The goal of this thesis is to give a better analysis of cycle toggling solver and to demystify its performance. First, techniques from vertex potential solvers will be used to improve the performance of cycle toggling solvers. Second, empirical results from the implementations of the solver of [KOSZ13] would be discussed. Finally, the solvers would be reanalyze using the framework of "Stochastic Dual Ascent" framework of [GR15] thereby establishing the connection of Laplacian Solvers with stochastic optimization.

36 pages

Thesis Committee:
Gary Miller (Chair)
David Woodruff

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]