An extension of the Munkres algorithm for the assignment problem to rectangular matrices

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An extension of the Munkres algorithm for the assignment problem to rectangular matrices

Full text

Pdf (253 KB)

Source

Communications of the ACM archive
Volume 14 , Issue 12 (December 1971) table of contents

Pages: 802 - 804

Year of Publication: 1971

ISSN:0001-0782

Authors

François Bourgeois	CERN, Geneva, Switzerland
Jean-Claude Lassalle	CERN, Geneva, Switzerland

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 24, Downloads (12 Months): 152, Citation Count: 17

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/362919.362945 What is a DOI?

ABSTRACT

The assignment problem, together with Munkres proposed algorithm for its solution in square matrices, is presented first. Then the authors develop an extension of this algorithm which permits a solution for rectangular matrices. Timing results obtained by using an adapted version of Silver's Algol procedure are discussed, and a relation between solution time and problem size is given.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Bourgeois, F., Grote, H., and Lassalle, J.C. Pattern recognition methods for Omega and SFM Spark Chamber experiments. CERN-Data Handling Division DD/DH/70/13, Geneva, Switzerland, Mar. 1970.
	2	Munkres, J. Algorithms for the assignment and transportation Problems. J. Siam 5 (Mar. 1957), 32-38.
	3	Roland Silver, An algorithm for the assignment problem, Communications of the ACM, v.3 n.11, p.605-606, Nov. 1960 [doi>10.1145/367436.367476]
	4	Berge, C. Thdorie des Graphes et ses Applications. Dunod, Paris, 1958.
	5	Kaufmann, A. Introduction ~ la Combinatorique en Vue de ses Applications. Dunod, Paris, 1968, pp. 506-515.

CITED BY 17

	C. P. Hsu , B. N. Tien , K. Chow , R. A. Perry , J. Tang, ALPS2: a standard cell layout system for double-layer metal technology, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.443-448, June 1985, Las Vegas, Nevada, United States
	Giorgio Carpaneto , Paolo Toth, Algorithm 548: Solution of the Assignment Problem [H], ACM Transactions on Mathematical Software (TOMS), v.6 n.1, p.104-111, March 1980
	F. Bourgeois , J. C. Lassalle, Algorithm 415: Algorithm for the assignment problem (rectangular matrices), Communications of the ACM, v.14 n.12, p.805-806, Dec. 1971
	Kiam Tian Seow , Khee Yin How, Collaborative assignment: a multiagent negotiation approach using BDI concepts, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy
	N. P. Chrisochoides , E. N. Houstis , C. E. Houstis, Geometry based mapping strategies for PDE computations, Proceedings of the 5th international conference on Supercomputing, p.115-127, June 17-21, 1991, Cologne, West Germany
	Jae-Chern Yoo , Young-Soo Kim, Alpha-beta-tracking index (α-β-Λ) tracking filter, Signal Processing, v.83 n.1, p.169-180, January 2003
	B. N. Tien , B. S. Ting , J. Cheam , K. Chow , S. C. Evans, GALA - an automatic layout system for high density CMOS gate arrays, Proceedings of the 21st conference on Design automation, p.657-662, June 25-27, 1984, Albuquerque, New Mexico, United States
	B. A. Carpenter , N. J. Davis, IV, Implementation and performance analysis of parallel assignment algorithms on a hypercube computer, Proceedings of the third conference on Hypercube concurrent computers and applications, p.1231-1235, January 1989, Pasadena, California, United States
	Wenliang Wu , Douglas C. Schmidt, A new routing algorithm for two-sided boards with floating vias, Proceedings of the 13th conference on Design automation, p.151-160, June 28-30, 1976, San Francisco, California, United States
	Douglas C. Schmidt, Gate for gate modular replacement of combinational switching networks, Proceedings of the 9th workshop on Design automation, p.331-340, June 26-28, 1972
	Jae-Chern Yoo , Young-Soo Kim, Data association and target identification using range profile, Signal Processing, v.84 n.3, p.571-587, March 2004
	Pavlina Konstantinova , Alexander Udvarev , Tzvetan Semerdjiev, A study of a target tracking algorithm using global nearest neighbor approach, Proceedings of the 4th international conference conference on Computer systems and technologies: e-Learning, p.290-295, June 19-20, 2003, Rousse, Bulgaria
	Dipankar Dasgupta , German Hernandez , Deon Garrett , Pavan Kalyan Vejandla , Aishwarya Kaushal , Ramjee Yerneni , James Simien, A comparison of multiobjective evolutionary algorithms with informed initialization and kuhn-munkres algorithm for the sailor assignment problem, Proceedings of the 2008 GECCO conference companion on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA
	Xiaoqiang Luo, On coreference resolution performance metrics, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.25-32, October 06-08, 2005, Vancouver, British Columbia, Canada
	Roland Hübscher, Computer-supported negotiation of course content, Computers & Education, v.53 n.3, p.726-732, November, 2009
	Kiam Tian Seow , Kwang Mong Sim, Collaborative assignment using belief-desire-intention agent modeling and negotiation with speedup strategies, Information Sciences: an International Journal, v.178 n.4, p.1110-1132, February, 2008
	Kaspar Riesen , Horst Bunke, Approximate graph edit distance computation by means of bipartite graph matching, Image and Vision Computing, v.27 n.7, p.950-959, June, 2009

INDEX TERMS

Keywords:
algorithm, assignment problem, operations research, optimization theory, rectangular matrices

Collaborative Colleagues:

François Bourgeois: colleagues

Jean-Claude Lassalle: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player