Title: Network Design $s$-$t$ Effective Resistance
| Speaker: | Hong Zhou |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
We consider a problem of designing a network with small $s$-$t$ effective resistance. In the problem, we are given an undirected graph $G=(V,E)$, two designated vertices $s,t \in V$, and a budget $k$. The goal is to choose a subgraph of $G$ with at most $k$ edges to minimize the $s$-$t$ effective resistance. This problem is an interpolation between the shortest path problem and the minimum cost flow problem and has applications in electrical network design.
Unlike the classic shortest path problem and min-cost flow problem, we show that the $s$-$t$ effective resistance network design problem is NP-hard. On the algorithmic side, we analyze a convex programming relaxation of the problem and design a constant factor approximation algorithm. The key of the rounding algorithm is a randomized path-rounding procedure based on the optimality conditions and a flow decomposition of the fractional solution.
Joint work with Pak Hay Chan, Lap Chi Lau, Aaron Schild and Sam Chiu-wai Wong.
Arxiv link of the manuscript: https://arxiv.org/abs/1904.03219.