Provable Guarantees for Power Loss Minimization in Electricity Distribution Networks

Motivated by reconfiguration of electricity distribution grids to reduce power losses to due electrical flow, we consider the minimization of a cubic objective over the spanning tree polytope (i.e. radial networks). This corresponds to a supermodular function minimization over a matroid basis constraint, for which there are no known multiplicative approximation algorithms. For the special case of the power loss objective, we provide simple approximation algorithms with provable guarantees for various settings: O(n) approximation using shortest-path trees for general graphs (with n nodes) with general demands, O(\sqrt{n}) approximation for grid graphs (with n nodes) with general demands using the cut structure, and a constant factor approximation for grid graphs with uniform demand. This is on-going joint work with Ali Khodabakhsh, Hassan Mortagy and Evdokia Nikolova.