{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:42:35Z","timestamp":1767339755230,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,7,31]],"date-time":"2022-07-31T00:00:00Z","timestamp":1659225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSERC Discovery","award":["2950-120715"],"award-info":[{"award-number":["2950-120715"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,7,31]]},"abstract":"<jats:p>\n            We consider a new problem of designing a network with small\n            <jats:italic>s<\/jats:italic>\n            -\n            <jats:italic>t<\/jats:italic>\n            effective resistance. In this problem, we are given an undirected graph\n            <jats:italic>G<\/jats:italic>\n            =\n            <jats:italic>(V,E)<\/jats:italic>\n            , two designated vertices\n            <jats:italic>s,t \u2208 V<\/jats:italic>\n            , and a budget\n            <jats:italic>k<\/jats:italic>\n            . The goal is to choose a subgraph of\n            <jats:italic>G<\/jats:italic>\n            with at most\n            <jats:italic>k<\/jats:italic>\n            edges to minimize the\n            <jats:italic>s<\/jats:italic>\n            -\n            <jats:italic>t<\/jats:italic>\n            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.\n          <\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3522588","type":"journal-article","created":{"date-parts":[[2022,3,17]],"date-time":"2022-03-17T13:36:20Z","timestamp":1647524180000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Network Design for\n            <i>s<\/i>\n            -\n            <i>t<\/i>\n            Effective Resistance"],"prefix":"10.1145","volume":"18","author":[{"given":"Pak Hay","family":"Chan","sequence":"first","affiliation":[{"name":"Google Waterloo, Waterloo, ON, Canada"}]},{"given":"Lap Chi","family":"Lau","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}]},{"given":"Aaron","family":"Schild","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}]},{"given":"Sam Chiu-Wai","family":"Wong","sequence":"additional","affiliation":[{"name":"Microsoft Research Redmond, Redmond, WA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0784-4073","authenticated-orcid":false,"given":"Hong","family":"Zhou","sequence":"additional","affiliation":[{"name":"Fuzhou University, Fuzhou, Fujian, China"}]}],"member":"320","published-online":{"date-parts":[[2022,10,11]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_5_2_2","DOI":"10.1137\/S0097539792236237"},{"doi-asserted-by":"publisher","key":"e_1_3_5_3_2","DOI":"10.1007\/s10107-019-01464-2"},{"doi-asserted-by":"publisher","key":"e_1_3_5_4_2","DOI":"10.1109\/FOCS.2015.11"},{"doi-asserted-by":"publisher","key":"e_1_3_5_5_2","DOI":"10.1137\/1.9780898718829"},{"doi-asserted-by":"publisher","key":"e_1_3_5_6_2","DOI":"10.1137\/S0036144503423264"},{"doi-asserted-by":"publisher","key":"e_1_3_5_7_2","DOI":"10.1017\/CBO9780511804441"},{"doi-asserted-by":"publisher","key":"e_1_3_5_8_2","DOI":"10.1145\/1374376.1374403"},{"doi-asserted-by":"publisher","key":"e_1_3_5_9_2","DOI":"10.1007\/BF01270385"},{"doi-asserted-by":"publisher","key":"e_1_3_5_10_2","DOI":"10.1137\/120902847"},{"doi-asserted-by":"publisher","key":"e_1_3_5_11_2","DOI":"10.1007\/s00493-006-0016-z"},{"doi-asserted-by":"publisher","key":"e_1_3_5_12_2","DOI":"10.1145\/1993636.1993674"},{"unstructured":"CBMS Regional Conference Series in Mathematics Spectral Graph Theory 92 Fan R. K. Chung 1997","key":"e_1_3_5_13_2"},{"doi-asserted-by":"publisher","key":"e_1_3_5_14_2","DOI":"10.1109\/FOCS.2009.38"},{"doi-asserted-by":"publisher","key":"e_1_3_5_15_2","DOI":"10.1137\/1.9781611974331.ch59"},{"doi-asserted-by":"publisher","key":"e_1_3_5_16_2","DOI":"10.1145\/301250.301447"},{"doi-asserted-by":"publisher","key":"e_1_3_5_17_2","DOI":"10.1007\/978-3-540-24698-5_63"},{"doi-asserted-by":"publisher","key":"e_1_3_5_18_2","DOI":"10.1145\/2591796.2591837"},{"doi-asserted-by":"publisher","key":"e_1_3_5_19_2","DOI":"10.1145\/1374376.1374401"},{"doi-asserted-by":"publisher","key":"e_1_3_5_20_2","DOI":"10.1109\/SFCS.2001.959908"},{"doi-asserted-by":"publisher","key":"e_1_3_5_21_2","DOI":"10.1137\/13094503X"},{"doi-asserted-by":"publisher","key":"e_1_3_5_22_2","DOI":"10.1007\/11496915_29"},{"doi-asserted-by":"publisher","key":"e_1_3_5_23_2","DOI":"10.1002\/net.20289"},{"doi-asserted-by":"publisher","key":"e_1_3_5_24_2","DOI":"10.1109\/CDC.2006.377282"},{"doi-asserted-by":"publisher","key":"e_1_3_5_25_2","DOI":"10.1137\/050645452"},{"key":"e_1_3_5_26_2","first-page":"223","volume-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201994)","author":"Goemans M. X.","year":"1994","unstructured":"M. X. Goemans, A. V. Goldberg, S. Plotkin, D. B. Shmoys, \u00c9. Tardos, and D. P. Williamson. 1994. Improved approximation algorithms for network design problems. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201994). Society for Industrial and Applied Mathematics, Philadelphia, PA, 223\u2013232. http:\/\/dl.acm.org\/citation.cfm?id=314464.314497."},{"doi-asserted-by":"publisher","key":"e_1_3_5_27_2","DOI":"10.1137\/S0097539793242618"},{"doi-asserted-by":"publisher","key":"e_1_3_5_28_2","DOI":"10.1287\/moor.17.1.36"},{"doi-asserted-by":"publisher","key":"e_1_3_5_29_2","DOI":"10.1109\/TPWRS.2011.2180406"},{"doi-asserted-by":"publisher","key":"e_1_3_5_30_2","DOI":"10.1007\/s004930170004"},{"key":"e_1_3_5_31_2","volume-title":"Treatise on Natural Philosophy","author":"Kelvin William Thomson Baron","year":"1867","unstructured":"William Thomson Baron Kelvin and Peter Guthrie Tait. 1867. Treatise on Natural Philosophy. Vol. 1. Clarendon Press."},{"doi-asserted-by":"publisher","key":"e_1_3_5_32_2","DOI":"10.1002\/andp.18471481202"},{"doi-asserted-by":"publisher","key":"e_1_3_5_33_2","DOI":"10.1145\/1806689.1806699"},{"doi-asserted-by":"publisher","key":"e_1_3_5_34_2","DOI":"10.1137\/S0097539702416736"},{"doi-asserted-by":"publisher","key":"e_1_3_5_35_2","DOI":"10.1137\/1.9781611973402.118"},{"doi-asserted-by":"publisher","key":"e_1_3_5_36_2","DOI":"10.1137\/070700620"},{"doi-asserted-by":"publisher","key":"e_1_3_5_37_2","DOI":"10.1007\/s10107-015-0858-5"},{"doi-asserted-by":"publisher","key":"e_1_3_5_38_2","DOI":"10.1145\/3357713.3384313"},{"doi-asserted-by":"publisher","key":"e_1_3_5_39_2","DOI":"10.1214\/aop\/1176991894"},{"doi-asserted-by":"publisher","key":"e_1_3_5_40_2","DOI":"10.1137\/1.9781611973730.134"},{"doi-asserted-by":"publisher","key":"e_1_3_5_41_2","DOI":"10.1137\/1.9781611975482.84"},{"unstructured":"Kaare Brandt Petersen and Michael Syskind Pedersen. 2012. The Matrix Cookbook. Retrieved from http:\/\/cw.matrixcookbook.com\/.","key":"e_1_3_5_42_2"},{"doi-asserted-by":"publisher","key":"e_1_3_5_43_2","DOI":"10.1016\/0022-0000(88)90003-7"},{"doi-asserted-by":"publisher","key":"e_1_3_5_44_2","DOI":"10.1145\/1806689.1806792"},{"doi-asserted-by":"publisher","key":"e_1_3_5_45_2","DOI":"10.1109\/CCC.2012.43"},{"doi-asserted-by":"publisher","key":"e_1_3_5_46_2","DOI":"10.1145\/3188745.3188852"},{"doi-asserted-by":"publisher","key":"e_1_3_5_47_2","DOI":"10.1214\/aoms\/1177729893"},{"doi-asserted-by":"publisher","key":"e_1_3_5_48_2","DOI":"10.1137\/080734029"},{"doi-asserted-by":"publisher","key":"e_1_3_5_49_2","DOI":"10.1137\/0211023"},{"key":"e_1_3_5_50_2","volume-title":"A Spectral Approach to Network Design and Experimental Design","author":"Zhou Hong","year":"2020","unstructured":"Hong Zhou. 2020. A Spectral Approach to Network Design and Experimental Design. Ph.D. Dissertation. University of Waterloo, Waterloo."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3522588","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3522588","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:33Z","timestamp":1750183773000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3522588"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,31]]},"references-count":49,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7,31]]}},"alternative-id":["10.1145\/3522588"],"URL":"https:\/\/doi.org\/10.1145\/3522588","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2022,7,31]]},"assertion":[{"value":"2020-12-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}