- Tytuł:
- A new polynomial-time implementation of the out-of-kilter algorithm using Minty’s lemma
- Autorzy:
- Ghiyasvand, M.
- Powiązania:
- https://bibliotekanauki.pl/articles/205633.pdf
- Data publikacji:
- 2014
- Wydawca:
- Polska Akademia Nauk. Instytut Badań Systemowych PAN
- Tematy:
-
network flows
minimum cost flow problem
out- of-kilter algorithm
Minty’s lemma - Opis:
- It is less well known how to use the out-of-kilter idea to solve the min-cost flow problem because the generic version of the out-of-kilter algorithm runs in exponential time, although it is the sort of algorithm that computers can do easily. Ciupala (2005) presented a scaling out-of-kilter algorithm that runs in polynomial time using the shortest path computation in each phase. In this paper, we present a new polynomial time implementation of out-of-kilter idea. The algorithm uses a scaling method that is different from Ciupala’s scaling method. Each phase of Ciupala’s method needs a shortest path computation, while our algorithm uses Minty’s lemma to transform all the out-of-kilter arcs into in-kilter arcs. When the given network is infeasible, Ciupala’s algorithm does not work, but our algorithm presents some information that helps to repair the infeasible network.
- Źródło:
-
Control and Cybernetics; 2014, 43, 1; 79-94
0324-8569 - Pojawia się w:
- Control and Cybernetics
- Dostawca treści:
- Biblioteka Nauki
Artykuł