Algoritmi di flusso massimo al minimo costo

Parrini, Alessandro (2009): Algoritmi di flusso massimo al minimo costo.

Abstract

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
• English Title: Maximum flow - minimum cost algorithms
• Language: Italian
• 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

References

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.