Networks are everywhere, changing the way we communicate with each 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.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:689179 |
| Date | January 2016 |
| Creators | Christofi, Michalis |
| Contributors | Steinhofel, Kathleen Kristine ; Radzik, Tomasz |
| Publisher | King's College London (University of London) |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | https://kclpure.kcl.ac.uk/portal/en/theses/sequential-and-distributed-algorithmic-frameworks-for-the-maximum-concurrent-flow-problem(73fe4087-a372-40cd-a11c-c92857b38c26).html |
Page generated in 0.0014 seconds