Parrini, Alessandro (2009): Algoritmi di flusso massimo al minimo costo.
Download (562kB) | Preview
This work concerns the maximum flows – minimum cost problem and its main algorithmic solutions. Such a problem involves determining the least cost shipment of a commodity through a capacitated network in order to satisfy demands at certain vertices using supplies available at other vertices. It generalizes both the shortest path problem and the maximum flow problem. The search for this particular flow can be obtained by interfacing the "maximum flow algorithm" (by Ford & Fulkerson) with a "shortest path algorithm" (we choose the one by Dijkstra): this will lead to two new algorithms: the "cycle-canceling algorithm" and "successive shortest path algorithm".
|Item Type:||MPRA Paper|
|Original Title:||Algoritmi di flusso massimo al minimo costo|
|English Title:||Maximum flow - minimum cost algorithms|
|Keywords:||maximum flow algorithm; shortest path problem; cycle-canceling algorithm; successive shortest path algorithm|
|Subjects:||C - Mathematical and Quantitative Methods > C4 - Econometric and Statistical Methods: Special Topics > C44 - Operations Research; Statistical Decision Theory
C - Mathematical and Quantitative Methods > C0 - General
C - Mathematical and Quantitative Methods > C6 - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling > C61 - Optimization Techniques; Programming Models; Dynamic Analysis
|Depositing User:||Alessandro Parrini|
|Date Deposited:||03. Jul 2012 06:26|
|Last Modified:||13. Feb 2013 00:49|
Brucker P. & Knust S. (2006), Complex Scheduling, Springer, Berlin.
Hillier, F. S. & Lieberman, G. J. (2005), Ricerca Operativa, McGraw-Hill, Milano.
Roses, K. H., Micheals, J. G., Gross, J. L., Grossman, J. W. & Shier D. R. (2000), Handbook of Discrete and Combinatorial Mathematics, CRC Press, Boca Raton, Florida.
Schrijver A. (2003), A course in Combinatorial Optimization, Lecture notes, Amsterdam.