Abstract
During the last two decades, several neural networks have been proposed for solving the assignment problem, and most of them either consist of O(n 2) neurons (processing units) or contain some time varying parameters. In the paper, based on the improved dual neural network proposed recently, we present a new assignment network with 2n neurons and some constant parameters only. Compared with the existing neural networks for solving the assignment problem, its more favorable for implementation. Numerical simulation results indicate that the time complexity of the network is O(n).
X. Hu’s work was supported by the National Natural Science Foundation of China under Grant Nos. 60805023 and 90820305, National Basic Research Program (973 Program) of China under Grant no. 2007CB311003, and Basic Research Foundation of Tsinghua National Laboratory for Information Science and Technology (TNList). J. Wang’s work was supported by the Research Grants Council of the Hong Kong Special Administrative Region, China, under Grants CUHK417209E and CUHK417608E.
Chapter PDF
Similar content being viewed by others
References
Bertsekas, D.P.: A new algorithm for the assignment problem. Math. Prog. 21(1), 152–171 (1981)
Balinski: Signature methods for the assignment problem. Operations Research 33(3), 527–536 (1985)
Eberhardt, S.P., Daud, T., Kerns, D.A., Brown, T.X., Thakoor, A.P.: Competitive neural architecture for hardware solution to the assignment problem. Neural Networks 4, 431–442 (1991)
Wang, J.: Analogue neural network for solving the assignment problem. Electronics Letters 28(11), 1047–1050 (1992)
Kosowsky, J.J., Yuille, A.L.: The invisible hand algorithm: solving the assignment problem with statistical physics. Neural Networks 7(3), 477–490 (1994)
Urahama, K.: Analog circuit for solving assignment problem. IEEE Trans. Circuits Syst. I 40, 426–429 (1994)
Wang, J.: Primal and dual assignment networks. IEEE Trans. Neural Netw. 8(3), 784–790 (1997)
Wang, J., Xia, Y.: Analysis and design of primal-dual assignment networks. IEEE Trans. Neural Netw. 9(1), 183–194 (1998)
Hu, X., Wang, J.: An improved dual neural network for solving a class of quadratic programming problems and its k-winners-take-all application. IEEE Trans. Neural Netw. 19(12), 2022–2031 (2008)
Kinderlehrer, D., Stampcchia, G.: An Introduction to Variational Inequalities and Their Applications. Academic, New York (1980)
Wang, J.: A deterministic annealing neural network for convex programming. Neural Networks 7(4), 629–641 (1994)
Hu, X., Zhang, B.: A new recurrent neural network for solving convex quadratic programming problems with an application to the k-winners-take-all problem. IEEE Trans. Neural Netw. 20(4), 654–664 (2009)
Hu, X., Zhang, B.: An alternative recurrent neural network for solving variational inequalities and related optimization problems. IEEE Trans. Syst., Man, Cybern. B 39(6), 1640–1645 (2009)
Cheng, L., Hou, Z.G., Tan, M.: A delayed projection neural network for solving linear variational inequalities. IEEE Trans. Neural Netw. 20(6), 915–925 (2009)
Forti, M., Nistri, P., Quincampoix, M.: Generalized neural network for nonsmooth nonlinear programming problems. IEEE Trans. Circuits Syst. I 51(9), 1741–1754 (2004)
Liu, Q., Wang, J.: A one-layer recurrent neural network with a discontinuous hard-limiting activation function for quadratic programming. IEEE Trans. Neural Netw. 19(4), 558–570 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hu, X., Wang, J. (2011). Solving the Assignment Problem with the Improved Dual Neural Network. In: Liu, D., Zhang, H., Polycarpou, M., Alippi, C., He, H. (eds) Advances in Neural Networks – ISNN 2011. ISNN 2011. Lecture Notes in Computer Science, vol 6675. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21105-8_63
Download citation
DOI: https://doi.org/10.1007/978-3-642-21105-8_63
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21104-1
Online ISBN: 978-3-642-21105-8
eBook Packages: Computer ScienceComputer Science (R0)