2026-09-20T20:51:16Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/98428 2023-07-11 col_2142_10761 col_2142_5131 com_2142_10755 com_2142_234 com_2142_5130

Chekuri, Chandra Idleman, Mark 2017-09-29T17:57:09Z 2017-09-29T17:57:09Z 2017-07-19 2017-08 Given a directed network G = (V,E) with source and target nodes s and t, respectively, and an integral capacity c_e on each edge e in E, an elementary k-flow is defined as a flow of 1 unit along each of k edge-disjoint s-t paths. A k-route flow, first introduced as a concept by Kishimoto, is defined as a non-negative linear sum of elementary k-flows. In this thesis, the study of k-route flows is extended by presenting efficient algorithms to calculate exact and approximate decompositions of k-route flows into their constituent elementary k-flows. In addition, such decomposition algorithms are shown to prove useful in developing approximation algorithms for the well-studied Minimum Congestion Routing Problem. Given a directed network G = (V,E), a set of source-sink pairs {(s_1, t_1), ..., (s_l, t_l)}, and an integer k, the goal of the Minimum Congestion Routing Problem is to find k edge-disjoint paths between each pair (s_i, t_i) while minimizing the congestion over all chosen paths (defined as the maximum over all edges of the number of chosen paths that share a single edge). Early applications of randomized rounding introduced by Raghavan and Tompson provided a simple approximation algorithm for the case where k=1, but attempts to achieve similar approximation bounds in the case where k>1 have up until this point required the use of more advanced dependent rounding schemes. Utilizing the k-route flow decomposition algorithms presented in this thesis, we propose approximation algorithms for the Minimum Congestion Routing Problem for the case where k>1 that mimic the straightforward approach of Raghavan and Tompson while achieving identical approximation guarantees. Finally, we implement two variants of the exact k-route flow decomposition algorithm proposed in this thesis, and experimentally compare their performance using flows generated from various graph structures. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2017-09-29 without embargo terms The student, Mark Idleman, accepted the attached license on 2017-07-19 at 15:08. The student, Mark Idleman, submitted this Thesis for approval on 2017-07-19 at 15:22. This Thesis was approved for publication on 2017-07-19 at 16:01. DSpace SAF Submission Ingestion Package generated from Vireo submission #11537 on 2017-09-29 at 11:32:17 Made available in DSpace on 2017-09-29T17:57:09Z (GMT). No. of bitstreams: 2 IDLEMAN-THESIS-2017.pdf: 359454 bytes, checksum: 2b852b219d5634faef87647565bccd52 (MD5) LICENSE.txt: 4209 bytes, checksum: 8ad8e3867802682f3590b552077cabf1 (MD5) Previous issue date: 2017-07-19 application/pdf http://hdl.handle.net/2142/98428 en Copyright 2017 Mark Idleman Minimum congestion routing K-route flow Network flow Flow Decomposition Approximation algorithms for the minimum congestion routing problem via k-route flows text text Computer Science Computer Science University of Illinois at Urbana-Champaign Thesis M.S.