PhD Seminar • Algorithms and Complexity — Network Design for s-t Effective ResistanceExport this event to calendar

Wednesday, February 19, 2020 — 1:30 PM EST

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. 

arXiv link to the manuscript

Location 
DC - William G. Davis Computer Research Centre
1304
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
  1. 2020 (52)
    1. May (1)
    2. April (1)
    3. March (6)
    4. February (22)
    5. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (220)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)