Computer Science Masters Thesis Presentation

  • HUI HAN CHIN
  • Masters Student
  • Computer Science Department
  • Carnegie Mellon University
Master's Thesis Presentation

A New View of Cycle Toggling Based Laplacian Solver

Electrical flow on a graph is a special type of flow which correspond to the physical interpretation of 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 which has resulted in breakthroughs in long-standing problems such as solving the Approximate Maximum Flow problem [CKMST10].

"The "Minimum energy electrical flow" problem on a weighted undirected graph is to find an electrical flow of minimum energy that satisfies demand on the vertices. This problem can be solved using Laplacian solvers in nearly linear time and there are many vertex potential based solvers that have been developed such as [KMP11, CKM+14]. In [KOSZ13], a “cycle toggling” electrical flow solver was introduced. It a simpler algorithm than current solvers while having a competitive asymptotic running time. However, when it was shown experimentally to have poorer performance than traditional optimization approaches despite having better theoretical performance.

The goal of this thesis is to give a better analysis of the near linear time, cycle toggling solver and to demystify its performance. The main tool for the analysis would be the framework of "Stochastic Dual Ascent" by Grower [GR15] and establish the connection between the solver and stochastic optimization. This would better integrate the later work on the cycle toggling solver such as Accelerated Coordinate Descent [LS13] as well as giving a better understanding the primal-dual nature of electrical flows. Next, we would show how techniques, such as solver-chains, from vertex potential solvers, can be used to improve the performance of the cycle toggling solver.

Finally, we would discuss the empirical results of applying the improvements.

Thesis Committee:
Gary Miller
David Woodruff

Copy of Thesis Document

For More Information, Please Contact: 
Keywords: