A parametric visualization software for the assignment problem

Authors

  • Charalampos Papamanthou University of Macedonia - Department of Applied Informatics, Thessaloniki, Greece
  • Konstantinos Paparrizos University of Macedonia - Department of Applied Informatics, Thessaloniki, Greece
  • Nikolaos Samaras University of Macedonia - Department of Applied Informatics, Thessaloniki, Greece

DOI:

https://doi.org/10.2298/YJOR0501147P

Keywords:

assignment problem, network simplex algorithm, visualization, computer algorithms

Abstract

In this paper we present a parametric visualization software used to assist the teaching of the Network Primal Simplex Algorithm for the assignment problem (AP). The assignment problem is a special case of the balanced transportation problem. The main functions of the algorithm and design techniques are also presented. Through this process, we aim to underline the importance and necessity of using such educational methods in order to improve the teaching of Computer Algorithms.

References

Achatz, H., Kleinschmidt, P., Paparrizos, K. (1991) A dual forest algorithm for the assignment problem. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 4, 1-10

Achatz, H., Paparrizos, K., Samaras, N., Tsiplidis, K. (2002) A forest exterior point algorithm for the assignment problems. u: Pardalos P.M., Migdalas A., Buckard A. [ur.] Combinatorial and Global Optimization, Word Scientific Publishing, 1-10

Akgul, M. (1987) A genuinely polynomial primal simplex algorithm for the assignment problem. Ankara: Bilikent University, Working Paper IEOR 87-07

Balinski, M.L., Gomory, R.E. (1964) A primal method for the assignment and transportation problems. Management Sciences, 10, 578-598

Barr, R.S., Glover, F., Klingman, D. (1977) The alternating basis algorithm for assignment problems. Mathematical Programming Series A, 13, 1, 1-13

Bertsekas, D. (1981) A new algorithm for the assignment problem. Mathematical Programming, 21, 152-171

Brown, M.H., Hershberger, J. (1998) Fundamental techniques for algorithm animation displays. u: Stasko T. J., Dominique J., Brown H. M., Price A. B. [ur.] Software Visualization: Programming as a Multimedia Experience, Cambridge, MA, itd: Massachusetts Institute of Technology Press, 137-143

Byrne, D.M., Catrambone, R., Stasko, T.J. (1996) Do algorithm animations aid learning?. u: 7th Annual Winter Text Conference, Jackson Hole, January

Corman, T.H., Leiserson, C.E., Rivest, R.L. (2001) Introduction to algorithms. Cambridge, MA, itd: Massachusetts Institute of Technology Press

Cunningham, W. (1976) A network simplex method. Mathematical Programming Series A, 11, 2, 105-116

Cunningham, W.H., Marsh, B.A. (1978) A primal algorithm for optimum matching. Mathematical Programming Study, 8, 50-72

Dantzig, B.G. (1951) Application of the simplex method to a transportation problem. u: Koopmans T. C. [ur.] Activity Analysis and Production and Allocation, New York: Willey, 359-373

Dantzig, G.B. (1963) Linear programming and extensions. Princeton, NJ: Princeton University Press

Dosios, K., Paparrizos, K., Papatzikos, N., Sifaleras, A. (2002) LinPro: An educational informational system for linear programming. u: Proceedings of 15th Pan-Hellenic Conference of Greek Operations Research Society, Tripoli, To be published

Hundhausen, D.C., Douglas, A.S., Stasko, T.J. (2002) A meta-study of algorithm visualization effectiveness. Journal of Visual Languages and Computing, 13, 3, 259-290

Hung, M.S., Rom, W.O. (1980) Solving the assignment problem by relaxation. Operations Research, 28, 4, 969-982

Jeffery, L.C. (1999) Program monitoring and visualization. Berlin, itd: Springer Verlag

Jensen, A.P., Barnes, J.W. (1987) Network flow programming. Krieger Pub. Co

Kehoe, C., Stasko, T.J., Taylor, A. (2001) Rethinking the evaluation of algorithm animations as learning aids: An observational study. International Journal of Human-Computer Studies, 54, 265-284

Khuri, S., Holzapfel, K. (2001) EVEGA: An educational visualization environment for graph algorithms. ACMSIGCSE Bulletin, 33, 3, 101-104

King, K.N. (2000) Java programming from the beginning. New York: W. W. Norton and Co

Kuhn, H.W. (1955) The Hungarian method for the assignment problem. Naval Research Logistics, 2, 83-97

Minieka, E., Evans, R.J. (1992) Optimization algorithms for networks and graphs. New York: Marcel Dekker

Paparrizos, K. (1996) A non improving simplex algorithm for transportation problems. Operations Research, 30, 1, 1-15

Paparrizos, K. (1991) An infeasible, exterior point, simplex algorithm for assignment problems. Mathematical Programming, 51, 45-54

Rosling, G., Naps, T.L. (2002) A tested for pedagogical requirements in algorithm visualizations. u: 7th annual Conference on Innovation and Technology in Computer Science Education ITICSE 2002 Aarhus, Denmark, 96-100

Warland, J. (1991) Communication networks: A first course. McGraw-Hill

Downloads

Published

2005-03-01

Issue

Vol. 15 No. 1 (2005)

Section

Research Articles

License

Copyright (c) YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.