Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/5899
Title: | Experimental evaluation of algorithmic solutions for the maximum generalised network flow problem |
Authors: | Radzik, T Yang, S |
Keywords: | Network optimisation;Network flow algorithms;Generalised flow;Experimental evaluation |
Issue Date: | 2001 |
Citation: | Technical Report (2001/54) |
Abstract: | The maximum generalised network flow problem is to maximise the net flow into a specified node in a network with capacities and gain-loss factors associated with edges. In practice, input instances of this problem are usually solved using general-purpose linear programming codes, but this may change because a number of specialised combinatoria generalised-flow algorithms have been recently proposed. To complement the knwon theoretical analyses of these algorithms, we develop their implementations and investigate their actual performance. We focus in this study on Goldfarb, Jin and Orlin's excess-scaling algorithm and Tardos and Wayne's push-relabel algorithm. We develop variants of these algorithms to implementations of simple, but non-polynomial, combinatorial algorithms proposed by Onaga and Truemper, and with performance of CPLEX, a commercial general-purpose linear progamming package. |
Description: | Also available as Technical Report No. TR-01-09, Department of Computer Science, King's College London, UK, 2001. |
URI: | http://www.cs.le.ac.uk/people/sy11/Papers/TR-2001-54.pdf http://bura.brunel.ac.uk/handle/2438/5899 |
Appears in Collections: | Publications Computer Science Dept of Computer Science Research Papers |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Fulltext.pdf | 322.84 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.