Please use this identifier to cite or link to this item:
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.
Appears in Collections:Publications
Computer Science
Dept of Computer Science Research Papers

Files in This Item:
File Description SizeFormat 
Fulltext.pdf322.84 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.