Hong
Zhou,
PhD
candidate
David
R.
Cheriton
School
of
Computer
Science
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.