• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Chan, Pak Hay (Chan, Pak Hay.) [1] | Lau, Lap Chi (Lau, Lap Chi.) [2] | Schild, Aaron (Schild, Aaron.) [3] | Wong, Sam Chiu-Wai (Wong, Sam Chiu-Wai.) [4] | Zhou, Hong (Zhou, Hong.) [5] (Scholars:周宏)

Indexed by:

SCIE

Abstract:

We consider a new problem of designing a network with small s-t effective resistance. In this problem, we are given an undirected graph G = (V, E), two designated vertices s, t is an element of 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. We present several algorithmic and hardness results for this problem and its variants. On the hardness side, we show that the problem is NP-hard, and the weighted version is hard to approximate within a factor smaller than two assuming the small-set expansion conjecture. 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. We also use dynamic programming to obtain a fully polynomial time approximation scheme when the input graph is a series-parallel graph, with better approximation ratio than the integrality gap of the convex program for these graphs.

Keyword:

Effective resistance network design

Community:

  • [ 1 ] [Chan, Pak Hay]Google Waterloo, Waterloo, ON, Canada
  • [ 2 ] [Lau, Lap Chi]Univ Waterloo, Waterloo, ON, Canada
  • [ 3 ] [Schild, Aaron]Univ Washington, Seattle, WA 98195 USA
  • [ 4 ] [Wong, Sam Chiu-Wai]Microsoft Res Redmond, Redmond, WA USA
  • [ 5 ] [Zhou, Hong]Fuzhou Univ, Sch Math & Stat, Fuzhou, Fujian, Peoples R China

Reprint 's Address:

Show more details

Related Keywords:

Related Article:

Source :

ACM TRANSACTIONS ON ALGORITHMS

ISSN: 1549-6325

Year: 2022

Issue: 3

Volume: 18

1 . 3

JCR@2022

0 . 9 0 0

JCR@2023

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:61

JCR Journal Grade:3

CAS Journal Grade:2

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 3

Online/Total:121/10070581
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1