Approximating multi-commodity max-flow in practice

Abstract: 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 Õ(mnϵ2). 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 Õ(m2ϵ2). 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 O(n(n+m)log2n), compared to the space complexity of Fleischer’s algorithm of O(n). 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.