{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T00:03:10Z","timestamp":1771372990605,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,4,3]],"date-time":"2018-04-03T00:00:00Z","timestamp":1522713600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS-1443905,EFRI-1441231"],"award-info":[{"award-number":["CNS-1443905,EFRI-1441231"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000774","name":"DTRA","doi-asserted-by":"crossref","award":["HDTRA1-14-0055"],"award-info":[{"award-number":["HDTRA1-14-0055"]}],"id":[{"id":"10.13039\/100000774","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2018,4,3]]},"abstract":"<jats:p>\n            Motivated by networked systems in which the functionality of the network depends on vertices in the network being within a bounded distance\n            <jats:italic>T<\/jats:italic>\n            of each other, we study the length-bounded multicut problem: given a set of pairs, find a minimum-size set of edges whose removal ensures the distance between each pair exceeds\n            <jats:italic>T<\/jats:italic>\n            . We introduce the first algorithms for this problem capable of scaling to massive networks with billions of edges and nodes: three highly scalable algorithms with worst-case performance ratios. Furthermore, one of our algorithms is fully dynamic, capable of updating its solution upon incremental vertex \/ edge additions or removals from the network while maintaining its performance ratio. Finally, we show that unless\n            <jats:italic>NP<\/jats:italic>\n            \u2286\n            <jats:italic>BPP<\/jats:italic>\n            , there is no polynomial-time, approximation algorithm with performance ratio better than $\u00d8mega (T)$, which matches the ratio of our dynamic algorithm up to a constant factor.\n          <\/jats:p>","DOI":"10.1145\/3179407","type":"journal-article","created":{"date-parts":[[2018,4,4]],"date-time":"2018-04-04T12:11:45Z","timestamp":1522843905000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Network Resilience and the Length-Bounded Multicut Problem"],"prefix":"10.1145","volume":"2","author":[{"given":"Alan","family":"Kuhnle","sequence":"first","affiliation":[{"name":"University of Florida, Gainesville, FL, USA"}]},{"given":"Victoria G.","family":"Crawford","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL, USA"}]},{"given":"My T.","family":"Thai","sequence":"additional","affiliation":[{"name":"University of Florida, Gainesville, FL, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,4,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Vijay V. Vazirani. Approximation Algorithms. Springer-Verlag Berlin Heidelberg first edition 2003.  Vijay V. Vazirani. Approximation Algorithms. Springer-Verlag Berlin Heidelberg first edition 2003.","DOI":"10.1007\/978-3-662-04565-7"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1177\/0160017607308679"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1715730.1715745"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2014.2300753"},{"key":"e_1_2_1_5_1","volume-title":"Thrybom and Gunnar Prytz. QoS in Switched Industrial Ethernet. IEEE Conference on Emerging Technologies and Factory Automation","author":"Linus","year":"2009"},{"key":"e_1_2_1_6_1","unstructured":"Amazon.com. Amazon.com Help: Guaranteed Delivery Terms and Conditions. https:\/\/www.amazon.com\/gp\/help\/customer\/display.html?ie=UTF8&nodeId=201910260. Accessed: 2017-10-01.  Amazon.com. Amazon.com Help: Guaranteed Delivery Terms and Conditions. https:\/\/www.amazon.com\/gp\/help\/customer\/display.html?ie=UTF8&nodeId=201910260. Accessed: 2017-10-01."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3078505.3078538"},{"key":"e_1_2_1_8_1","unstructured":"Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/ data. Accessed: 2017--10-01.  Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/ data. Accessed: 2017--10-01."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/wcm.1219"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2017.2684807"},{"key":"e_1_2_1_12_1","unstructured":"Euiwoong Lee. Improved Hardness for Cut Interdiction and Firefighter Problems. Arxiv preprint arxiv:1607.05133v1 2016.  Euiwoong Lee. Improved Hardness for Cut Interdiction and Firefighter Problems. Arxiv preprint arxiv:1607.05133v1 2016."},{"key":"e_1_2_1_13_1","unstructured":"Michael Sipser. Introduction to the Theory of Computation. Thomson Course Technology second edition 2006.  Michael Sipser. Introduction to the Theory of Computation. Thomson Course Technology second edition 2006."},{"key":"e_1_2_1_14_1","unstructured":"Alan Kuhnle. Source code link. https:\/\/gitlab.com\/kuhnle\/multi-pcut.  Alan Kuhnle. Source code link. https:\/\/gitlab.com\/kuhnle\/multi-pcut."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1868237.1868241"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2010.09.009"},{"key":"e_1_2_1_17_1","first-page":"452","volume-title":"Dvorak and Dusan Knop. Parameterized Complexity of Length-Bounded Cuts and Multi-cuts. In Theory and Applications of Models of Computation: 12th Annual Conference","author":"Pavel"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm048"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90065-5"},{"issue":"2","key":"e_1_2_1_20_1","first-page":"97","volume":"40","author":"Israeli Eitan","year":"2002","journal-title":"Kevin Wood. Shortest-Path Network Interdiction. Networks"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1245581.1245586"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12061-010-9057-1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167266"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644181"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250888"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00142"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-009-9269-y"},{"key":"e_1_2_1_28_1","unstructured":"T. Soma and Y. Yoshida. A Generalization of Submodular Cover via the Diminishing Return Property on the Integer Lattice. Advances in Neural Information Processing ... pages 1--9 2015.   T. Soma and Y. Yoshida. A Generalization of Submodular Cover via the Diminishing Return Property on the Integer Lattice. Advances in Neural Information Processing ... pages 1--9 2015."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2010.05.010"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2744769.2747942"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/MILCOM.2001.985795"},{"key":"e_1_2_1_32_1","volume-title":"IEEE Military Communications Conference (MILCOM). IEEE","author":"Syed","year":"2013"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCOM.2006.248164"},{"key":"e_1_2_1_34_1","first-page":"2","volume-title":"Electronic Colloquium on Computation Complexity (ECCC)","volume":"21","author":"Guruswami Venkatesan","year":"2014"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2006.890089"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOM.2010.5683938"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.2000.869794"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3179407","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3179407","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3179407","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:17Z","timestamp":1750208897000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3179407"}},"subtitle":["Reaching the Dynamic Billion-Scale with Guarantees"],"short-title":[],"issued":{"date-parts":[[2018,4,3]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,4,3]]}},"alternative-id":["10.1145\/3179407"],"URL":"https:\/\/doi.org\/10.1145\/3179407","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,3]]},"assertion":[{"value":"2018-04-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}