We will present the first provable approximation guarantees for the network reconfiguration problem from power systems. The problem seeks to find a tree T such that the energy of the (unique) feasible electrical flow with support T is minimized. The tree requirement on the support of the flow is motivated by operational constraints in electricity distribution networks. The bulk of existing results on the structure of electrical flows do not easily give guarantees for this problem, while many heuristic methods have been used in the power systems community as early as 1989. Our main contribution is to advance the theory for network reconfiguration by providing novel lower bounds and corresponding approximation factors for various settings ranging from O(n) for general graphs, to O(\sqrt(n)) over grids with uniform resistances on edges, and O(1) for grids with uniform edge resistances and demands. We also provide a new method for (approximate) graph sparsification that maintains the original resistances of the edges.

This is joint work with Hassan Mortagy, Ali Khodabakhsh and Evdokia Nikolova.