A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem

Konstantinos Paparrizos

RAIRO - Operations Research - Recherche Opérationnelle (1988)

  • Volume: 22, Issue: 3, page 269-289
  • ISSN: 0399-0559

How to cite

top

Paparrizos, Konstantinos. "A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem." RAIRO - Operations Research - Recherche Opérationnelle 22.3 (1988): 269-289. <http://eudml.org/doc/104943>.

@article{Paparrizos1988,
author = {Paparrizos, Konstantinos},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {signature methods; dual relaxation procedure; assignment; consecutive stages},
language = {eng},
number = {3},
pages = {269-289},
publisher = {EDP-Sciences},
title = {A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem},
url = {http://eudml.org/doc/104943},
volume = {22},
year = {1988},
}

TY - JOUR
AU - Paparrizos, Konstantinos
TI - A non-dual signature method for the assignment problem and a generalization of the dual simplex method for the transportation problem
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 1988
PB - EDP-Sciences
VL - 22
IS - 3
SP - 269
EP - 289
LA - eng
KW - signature methods; dual relaxation procedure; assignment; consecutive stages
UR - http://eudml.org/doc/104943
ER -

References

top
  1. 1. M. L. BALINSKI, Signatures des points extrêmes du polyhèdres dual du problème de transport, C.R. Acad. Sci. Paris, 296, Série I, pp. 456-459, 1983. Zbl0527.90069MR701910
  2. 2. M. L. BALINSKI, Signature Methods for the Assignment Problem, Operations Research, 33, 1985, pp. 527-537. Zbl0583.90064MR791705
  3. 3. M. L. BALINSKI, A Competitive (dual) Simplex Method for the Assignment Problem, Mathematical Programming, 34, 1986, pp. 125-141. Zbl0596.90064MR838474
  4. 4. M. L. BALINSKI and R. E. GOMORY, A Primal Method for the Assignment and Transportation Problems, Management Science, 10, 1964, pp. 578-593. 
  5. 5. R. BARR, F. GLOVER and D. KLINGMAN, The Alternating path Basis Algorithm for Assignment Problems, Mathematical Programming, Vol. 13, 1977, pp. 1-13. Zbl0378.90097MR444039
  6. 6. D. BERTSEKAS, A new algorithm for the Assignment Problem, Mathematical Programming, Vol. 21, 1981, pp. 152-171. Zbl0461.90069MR623835
  7. 7. W. H. CUNNINGHAM, A Network Simplex Method, Mathematical Programming, Vol. 11, 1976, pp. 105-116. Zbl0352.90039MR462532
  8. 8. W. H. CUNNINGHAM and A. B. MARSH, III, A Primai Algorithm for Optimum Matching, Mathematical Programming Study, 8, 1978, pp. 50-72. Zbl0409.90081
  9. 9. E. A. DINIC and M. A. KRONRAD, An Algorithm for the Solution of the Assignment Problem, Soviet Mathematics Doklady, Vol. 10, 1969, pp. 248-264. Zbl0213.44801
  10. 10. J. ENDMONDS and R. M. KARP, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the Association for Computing Machinery, Vol. 19, 1972, pp. 248-264. Zbl0318.90024
  11. 11. L. R. FORD and D. R. FULKERSON, Flows in Networks, Princeton University Press, Princeton, 1962. Zbl0106.34802MR159700
  12. 12. D. GOLDFARB, Efficient dual Simplex Methods for the Assignment Problem, Mathematical Programming, Vol. 33, 1985, pp. 127-203. Zbl0578.90051MR808910
  13. 13. M. S. HUNG, A Polynomial Simplex Method for the Assignment Problem, Operations Research, Vol. 31, 1983, pp. 595-600. Zbl0519.90056MR709237
  14. 14. M. S. HUNG and W. O. ROM, Solving the Assignment Problem by Relaxation, Operations Research, Vol. 28, 1980, pp. 969-982. Zbl0441.90062MR584900
  15. 15. H. W. KUHN, The Hungarian Method for the Assignment Problem, Naval Research Logistics Quarterly, Vol. 2, 1955, pp. 83-97. Zbl0143.41905MR75510
  16. 16. E. LAWLER, Combinatorial Optimization, Network and Matroids, Holt, Rinchart and Winston, New York, 1976. Zbl0413.90040MR439106
  17. 17. J. MUNKRES, Algorithms for the Assignment and Transportation Problems, S.I.A.M. Journal, Vol. 5, 1957, pp. 83-97. Zbl0083.15302MR93429
  18. 18. E. ROOHY-LALEH, Improvement to the Theoretical Efficiency of the Network Simplex Method, Ph. D. Thesis, Carleton University, 1981. MR2631943
  19. 19. V. SRINIVASEN and G. L. THOMSON, Cost Operator Algorithms for the Transportation Problem, Mathematical Programming, Vol. 12, 1977, pp. 372-391. Zbl0362.90058MR451730
  20. 20. G. L. THOMSON, A Recursive Method for the Assignment Problems, Annals of Discrete Mathematics, Vol. 11, 1981, pp. 319-343. Zbl0469.90051
  21. 21. N. TOMIZAWA, On some Techniques Usefull for Solution of Transportation Network Problems, Network, Vol. 1, 1972, pp. 173-194. Zbl0253.90015MR297347

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.