BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Ghiyasvand Mehdi (Bu-Ali Sina University, Hamedan, Iran)
A New Polynomial-Time Implementation of the Out-of-Kilter Algorithm Using Minty's Lemma
Control and Cybernetics, 2014, vol. 43, nr 1, s. 79-94, rys., bibliogr. s. 93-94
Słowa kluczowe
Programowanie matematyczne, Algorytmy
Mathematical programming, Algorithms
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. (original abstract)
Dostępne w
Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie
Biblioteka Szkoły Głównej Handlowej
Pełny tekst
  1. AHUJA R.K., GOLDBERG A.V., ORLIN J.B. and TARJAN R.E. (1992), Finding minimum-cost flows by double scaling. Mathematical Programming 53, 243-266.
  2. AHUJA R.K., MAGNANTI T.L. and ORLIN J.B. (1993) Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs, NJ.
  3. BUSAKER R.G. and GOWEN P.J. (1961) A procedure for Determining a Family of minimal-cost Network Flow patterns. Technical Report 15, O.R.O.
  4. CIUPALA L. (2005) A scaling out-of-kilter algorithm for minimum cost flow. Control and Cybernetics 34(4), 1169-1174.
  5. EDMONDS I. and KARP R.M. (1972) Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the Association on Computing Machinery 19, 248-264.
  6. ERVOLINA T.R. and MCCORMICK S.T. (1993) Two strongly polynomial cut canceling algorithms for minimum cost network flow. Discrete Applied Mathematics 46, 133-5.
  7. FULKERSON D.R. (1961) An out-of-kilter method for minimal cost flow problems. SIAM Journal on Applied Mathematics 9, 18-27.
  8. GOLDBERG A.V and TARJAN R.E. (1990) Finding minimum-cost circulations by successive approximation. Mathematics of Operations Research 16, 430-466.
  9. GONDRAN M. and MINOUX M. (1984) Graphs and Algorithms (trans. S. Vajda). Wiley, New York.
  10. HASSIN R. (1983) The minimum cost flow problem: A unifying approach to dual algorithms and a new tree search algorithm. Mathematical Programming 25, 228-239.
  11. HOFFMAN A.J. (1960) Some recent applications of the theory of linear in- equalities to extremal combinatorial analysis. In: R. Bellman and M. Hall (eds.), Combinatorial Analysis. Proc. of Symposia in Applied Mathematics, X. American Mathematical Society, Providence, Rhode Island, 113-127.
  12. JEWELL W.S. (1958) Optimal Flow through Networks. Technical Report 8, M.I.T.
  13. MINTY G.J. (1960) Monotone networks. Proc. Roy. Soc. London, 257, 194-212.
  14. MINTY G.J. (1966) On the Axiomatic Foundations of the Theories of Directed linear Graphs, Electrical Networks and Programming. Journal of Mathematics and Mechanics 15, 485-520.
  15. ORLIN J.B. (1993) A faster strongly polynomial minimum cost flow algorithm. Operations Research, 41, 338 350.
Cytowane przez
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu