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., and Paparrizos, K., “A dual forest algorithm for the assignment problem”, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 4 (1991) 1-10.

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

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

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

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

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

Brown, M.H., and Hershberger, J., “Fundamental techniques for algorithm animation displays”, in: Stasko, T.J., Dominique, J., Brown, H.M., and Price, A.B., (eds.), Software Visualization: Programming as a Multimedia Experience, MIT Press, 1998, 137-143.

Byrne, D.M., Catrambone, R., and Stasko, T.J., “Do algorithm animations aid learning?”, 7th Annual Winter Text Conference, Jackson Hole, January, 1996.

Cormen, T.H., Leiserson, C.E., and Rivest, R.L., Introduction to Algorithms, 2nd edition, MIT Press, 2001.

Cunningham, W.H., “A network simplex method”, Mathematical Programming, 11 (1976) 105-116.

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

Dantzig, B.G., “Application of the simplex method to a transportation problem”, in: Koopmans, T.C. (ed.), Activity Analysis and Production and Allocation, Willey, N.Y., 1951, 359-373.

Dantzig, B.G., Linear Programming and Extensions, Princeton University Press, Princeton, NJ, 1963.

Dosios, K., Paparrizos, K., Papatzikos, N., and Sifaleras, A., “LinPro, an educational informational system for linear programming”, To be published in Proceedings of 15th Pan Hellenic Conference of Greek Operations Research Society, Tripoli, 2002.

http://ccwf.cc.utexas.edu/~sakshi/ Univ. of Texas, Austin.

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

Hung, M.S., and Rom, W.D., “Solving the assignment problem by relaxation”, Operations Research, 28 (1980) 969-982.

Jeffery, L.C., Program Monitoring and Visualization, Springer-Verlag, New York, 1999.

Jensen, A.P., and Barnes, J.W., Network Flow Programming, Krieger Pub. Co., 1987.

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

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

King, K.N., Java Programming from the Beginning, W.W. Norton & Co., New York, 2000.

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

Minieka, E., and Evans, R.J., Optimization Algorithms for Networks and Graphs, 2nd edition, Marcel Dekker, New York, 1992.

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

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

Rößling, G., Naps, T.L., “A tested for pedagogical requirements in algorithm visualizations”, 7th annual Conference on Innovation and Technology in Computer Science Education ITICSE 2002, Aarhus, Denmark, 2002, 96-100.

Warland, J., Communication Networks: A First Course, McGraw-Hill, 1991.

Downloads

Published

2005-03-01

Issue

Vol. 15 No. 1 (2005)

Section

Research Articles

License

Copyright (c) 2005 YUJOR

Creative Commons License

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