- Tytuł:
- A scaling out-of-kilter algorithm for minimum cost flow
- Autorzy:
- Ciupala, L.
- Powiązania:
- https://bibliotekanauki.pl/articles/970996.pdf
- Data publikacji:
- 2005
- Wydawca:
- Polska Akademia Nauk. Instytut Badań Systemowych PAN
- Tematy:
-
network flow
minimum cost flow
shortest path
scaling technique - Opis:
- 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.
- Źródło:
-
Control and Cybernetics; 2005, 34, 4; 1169-1174
0324-8569 - Pojawia się w:
- Control and Cybernetics
- Dostawca treści:
- Biblioteka Nauki
Artykuł