Abstract
Networks are everywhere, changing the way we communicate witheach other, transport goods and share information. The problems of
efficient operation of such networks can often be stated as (abstract)
network flow problems. In a problem of this type we want to send
some commodity (goods, messages, data, electricity, vehicles) from
supply points to demand points in an underlying network, which is
modeled as a graph. There are various constraints on the characteristics
of the routes, such as capacities and costs. There may be a
number of different optimization objectives, depending on the problem
setting. Network flow problems form one of the most important and
most frequently encountered classes of optimization problems. They
lie at the intersection of several scientific fields including computer science,
mathematics and operational research. We are interested in the
computer science aspect of network optimization problems, that is, in
development and analysis of efficient algorithms for such problems.
In this thesis we study algorithmic frameworks for multicommodity
flow problems, which can be described in the following way. The input
is a directed graph G = (N; E), where N is the set of nodes and
E is the set of edges, and specifications of k commodities. Each edge
has an associated capacity c(e) and each commodity has an associated
source-sink pair of nodes (si; ti) and a demand value di. The
goal is to design simultaneous flow of all commodities that satisfies
their demands, takes into account the capacities of the edges and optimizes
a specified objective function. We focus on the problem of
minimizing the overall congestion, which is often referred to as the
Maximum Concurrent Flow problem. We consider both sequential
and distributed models of computation. We show that the two main
sequential algorithmic Maximum Concurrent Flow frameworks - the
rerouting framework and the incremental framework - are more closely
related than previously assumed. We prove that the running time of
some distributed Maximum Concurrent Flow algorithms shown recently
are asymptotically tight. We also propose a heuristic for these
algorithms to improve their performance on some types of inputs.
| Date of Award | 2016 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Kathleen Steinhofel (Supervisor) & Tomasz Radzik (Supervisor) |