Approximation algorithms for the minimum congestion routing problem via k-route flows

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2017

Author dc:creator

• Idleman, Mark

Contributors dc:contributor

• Chekuri, Chandra

• Minimum congestion routing
• K-route flow
• Network flow
• Flow
• Decomposition

Statement dc:rights

• Copyright 2017 Mark Idleman

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/98428

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/98428