×
Paparrizos, Konstantinos

An infeasible (exterior point) simplex algorithm for assignment problems. (English) Zbl 0734.90055

Math. Program., Ser. A 51, No. 1, 45-54 (1991).
The author presents an exterior point simplex method for assignment problems. This method is based on infeasible paths: any two basic feasible solutions can be connected with short simplex paths passing through an infeasible region.
Reviewer: V.D.Mazurov (Sverdlovsk)

Cited in 2 Reviews
Cited in 22 Documents

MSC:

90C05 Linear programming
90B80 Discrete location and assignment
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Keywords:

exterior point simplex method; assignment; infeasible paths
PDF BibTeX XML Cite
\textit{K. Paparrizos}, Math. Program. 51, No. 1 (A), 45--54 (1991; Zbl 0734.90055)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] M.L. Balinski, ”The Hirsch conjecture for dual transportation polyhedra,”Mathematics of Operations Research 9 (1984) 629–633. · Zbl 0555.90071
[2] M.L. Balinski, ”Signature methods for the assignment problem,”Operations Research 33 (1985) 527–536. · Zbl 0583.90064
[3] M.L. Balinski, ”A competitive (dual) simplex method for the assignment problem,”Mathematical Programming 34 (1986) 125–141. · Zbl 0596.90064
[4] R. Barr, F. Glover and D. Klingman, ”The alternating path basis algorithm for the assignment problem,”Mathematical Programming 13 (1977) 1–13. · Zbl 0378.90097
[5] W.H. Cunningham, ”A network simplex method,”Mathematical Programming 11 (1976) 105–116. · Zbl 0352.90039
[6] G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).
[7] G.B. Dantzig, ”Eight unsolved problems from mathematical programming,”Bulletin of the American Mathematical Society 70 (1964) 499–500.
[8] L.R. Ford and D.R. Fulkerson, ”Constructing maximal dynamic flows from static flows,”Operations Research 6 (1958) 419–433. · Zbl 0995.90516
[9] L.R. Ford and D.R. Fulkerson,Flows in Networks (Princeton University Press, Princeton, NJ, 1962). · Zbl 0106.34802
[10] M.L. Fredman and R.E. Tarjan, ”Fibonacci heaps and their uses in network optimization algorithms,”25th IEEE Symposium on Foundations of Computer Science (1984) 338–346.
[11] M.S. Hung and W.O. Rom, ”Solving the assignment problem by relaxation,”Operations Research 28 (1980) 969–982. · Zbl 0441.90062
[12] P. Kleinschmidt, C.W. Lee and H. Schannath, ”Transportation problems which can be solved by the use of Hirsch-paths for the dual problems,”Mathematical Programming 37 (1987) 153–168. · Zbl 0642.90070
[13] K. Paparrizos, ”A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem,”RAIRO Operations Research 22 (1988) 269–289. · Zbl 0664.90055
[14] P.M. White, A.S. Caplin and L. Van der Heyden, ”Scarf’s procedure for integer programming and a dual simplex algorithm,”Mathematics of Operations Reseach 10 (1985) 439–449. · Zbl 0583.90071
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.