A scaling out-of-kilter algorithm for minimum cost flow

• Autorzy: Ciupala L.
• Języki publikacji: EN

Abstrakty

EN

The out-of-kilter algorithm is one of the basic algorithms that solve the minimum cost flow problem. Its drawback is that it can improve the objective function at each iteration by only a small value. Consequently, it runs in pseudo-polynomial time. In this paper, we describe a new out-of-kilter algorithm for minimum cost flow that runs in polynomial time. Our algorithm is a scaling algorithm and improves the objective function at each time by a "sufficiently large" value.

Słowa kluczowe

EN

network flow; minimum cost flow; shortest path; scaling technique

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2005
• Tom: Vol. 34, no 4
• Strony: 1169--1174
• Opis fizyczny: Bibliogr. 6 poz.

Twórcy

autor

Ciupala L.

• Faculty of Mathematics and Informatics, Transilvania University of Brasov, Juliu Maniu 50, Romania

Bibliografia

• Ahuja, R., Magnanti, T. and Orlin, J.(1993) Network Flow. Theory, Algorithms and Applications. New Jersey, Prentice Hall.
• Ciupala, L.(2004) About universal maximal dynamic flows. Annals of University of Bucharest 53 (1), 115-124.
• Ciurea, E. and Ciupala, L.(2004) Sequential and parallel algorithms for minimum flows. Journal of Applied Mathematics and Computing 15 (1-2), 53-78.
• Ciurea, E. and Ciupala, L. (2001) Algorithms for minimum flows. Computer Science Journal of Moldova 9 (3), 275-290.
• Hoppe, B. and Tardos, E.(1994) Polynomial time algorithms for some evacuation Problems. Proceedings of the Fifth Annual ACM- SIAM Symposium on Discrete Algorithms, 433-441.
• Sokkalingam, P.T., Ahuja, R. and Orlin, J.(2001) New Polynomial-Time Cycle-Canceling Algorithms for Minimum Cost Flows. http://web.mit.edu/jorlin/www/papers.html