Files in this item
Files  Description  Format 

application/pdf IDLEMANTHESIS2017.pdf (359kB)  (no description provided) 
Description
Title:  Approximation algorithms for the minimum congestion routing problem via kroute flows 
Author(s):  Idleman, Mark 
Advisor(s):  Chekuri, Chandra 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  M.S. 
Genre:  Thesis 
Subject(s):  Minimum congestion routing
Kroute flow Network flow Flow Decomposition 
Abstract:  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 kflow is defined as a flow of 1 unit along each of k edgedisjoint st paths. A kroute flow, first introduced as a concept by Kishimoto, is defined as a nonnegative linear sum of elementary kflows. In this thesis, the study of kroute flows is extended by presenting efficient algorithms to calculate exact and approximate decompositions of kroute flows into their constituent elementary kflows. In addition, such decomposition algorithms are shown to prove useful in developing approximation algorithms for the wellstudied Minimum Congestion Routing Problem. Given a directed network G = (V,E), a set of sourcesink 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 edgedisjoint 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 kroute 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 kroute flow decomposition algorithm proposed in this thesis, and experimentally compare their performance using flows generated from various graph structures. 
Issue Date:  20170719 
Type:  Text 
URI:  http://hdl.handle.net/2142/98428 
Rights Information:  Copyright 2017 Mark Idleman 
Date Available in IDEALS:  20170929 
Date Deposited:  201708 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois