Change search
ReferencesLink to record
Permanent link

Direct link
Approximating multi-commodity max-flow in practice
KTH, School of Computer Science and Communication (CSC).
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Approximera multi-commodity max-flow i praktiken (Swedish)
Abstract [en]

Garg and Könemann developed a framework for computing multi-commodity maximum flow in a graph, later called a multiplicative weight update framework. Madry used this framework and exchanged Dijkstra’s algorithm to a dynamic graph algorithm for approximating the shortest paths through the graph. With this approachhe developed the fastest algorithm to date for calculating the multi-commodity maximum flow, with a running time of . This project have implemented the algorithm and compared it with a slightly modified version of the former fastest algorithm by Fleischer with a time complexity of . The results show that Madry’s algorithms is slower than Fleischer’s algorithm in practice for graph with less than 100 million edges. This project also computed the space needed for the dynamic algorithms used in Madry’s algorithm and can show a resulting space complexity of , compared to the space complexity of Fleischer’s algorithm of . For a graph with 100 million edges, 50 million Gb of space is needed to use Madry’s algorithm, which is more than our test computers had. We can therefore conclude that Madry’s algorithm is not usable in real life today, both in terms of memory usage and time consumption.

Abstract [sv]

Garg and Könemann utvecklade ett framework för att beräkna multi-commodity maximum flöde i en graf sedan kallat ett multiplicative weight update framework. Madry använde detta framework och bytte ut Dijkstra’s algoritm mot en dynamisk grafalgoritm för att kunna approximera kortaste vägen i grafen. Med detta angeppssätt utvecklade han den idag snabbaste algoritmen för beräkning av multicommodity maximum flöde med en tids komplexitet på . Det här projektet har implementerat hans algoritm och jämfört den med den tidigare snabbaste algoritmen skapad av Fleischer med en tidskomplexitet på . Resultatet visar att Madrys algoritm är långsammare än Fleischers algoritm i praktiken för grafer med färre än 100 miljoner kanter. Detta projekt beräknade också minnesåtgången för de dynamiska algoritmerna i Madrys algorithm och kan visa en resulterade minneskomplexitet på , jämfört med Fleischers algoritm på . För en graf med 100 miljoner kanter så behövs 50 miljoner Gb av minne för att kunna använda Madrys algoritm, vilket var mer än våra testdatorer hade. Vi kan därför konstatera att Madrys algoritm inte är användbar i praktiken idag, både när det kommer till minnesanvändning och till tidsåtgång.

Place, publisher, year, edition, pages
Keyword [en]
multi-commodity, maximum flow, max flow, flow, multicommodity, approximation, schemes, framework, dynamic graph, dynamic, ES-tree, complexity, space, time, Madry
Keyword [sv]
multicommodity, maximum flöde, max flöde, flöde, approximering, framework, dynamiska grafer, graf, dynamiskgraf, ES-träd, tidskomplexitet, komplexitet, minneskomplexitet, Madry
National Category
Computer Science
URN: urn:nbn:se:kth:diva-184193OAI: diva2:915549
Educational program
Master of Science in Engineering - Computer Science and Technology
Available from: 2016-04-06 Created: 2016-03-30 Last updated: 2016-04-06Bibliographically approved

Open Access in DiVA

fulltext(1300 kB)83 downloads
File information
File name FULLTEXT01.pdfFile size 1300 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 83 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 499 hits
ReferencesLink to record
Permanent link

Direct link