A parallel shortest augmenting path algorithm for the assignment problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A parallel shortest augmenting path algorithm for the assignment problem

Full text

Pdf (1.35 MB)

Source

Journal of the ACM (JACM) archive
Volume 38 , Issue 4 (October 1991) table of contents

Pages: 985 - 1004

Year of Publication: 1991

ISSN:0004-5411

Authors

Egon Balas	Carnegie-Mellon Univ., Pittsburgh, PA
Donald Miller	E. I. Du Pont de Nemours and Co., Inc.
Joseph Pekny	Purdue Univ., West Lafayette, IN
Paolo Toth	Univ. of Bologna, Bologna, Italy

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 98, Citation Count: 5

Additional Information:

references cited by index terms review 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/115234.115349 What is a DOI?

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	BALAS, E. AND TOTH~ P. Branch and bound methods. In E. L. Lawler, et al., The Traveling Salesman Problem: A Guided Tour to Combinatorial Optimization. Wiley, New York, 1985.
	2	M L Balinski, A competitive (dual) simplex method for the assignment problem, Mathematical Programming: Series A and B, v.34 n.2, p.125-141, March 1986 [doi>10.1007/BF01580579]
	3	BARR, R. S., GLOVER, F., AND KLINGMAN, D. The alternating basis algorithm for assignment problems. Math. Prog. 13 (1977), 1-13.
	4	BERTSEKAS, D. P. A new algorithm for the assignment problem. Math. Prog. 21 (1981), 152-171.
	5	BERTSEKAS, D. P., AND CASTANON, D.A. Parallel synchronous and asynchronous implementations of the auction algorithm. Electrical Engineering and Computer Science. MIT, Cambridge, Mass., 1989.
	6	R. E. Burkhard , U. Derigs, Assignment and Matching Problems: Solution Methods with FORTRAN-Programs, Springer-Verlag New York, Inc., Secaucus, NJ, 1980
	7	CARPANETO, G., AND TOTH, P. Algorithm for the solution of the assignment problem for sparse matrices. Comp. 31 (1983), 83-94.
	8	CARPANETO, G., AND TOTH, P. Primal-dual algorithms for the assignment problem. Disc. App. Math. 18, (1987), 137-153.
	9	DERIas, U. The shortest augmenting path method for solving assignment problems -- motivanon and computational experience. Ann. Op. Res. 4 (I985), 57-i02.
	10	DIJKSTRA, E.W. A note on two problems in connection with graphs. Numer. Math. 1 (1959), 269-271.
	11	Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
	12	FORD, L. R., AND FULKERSON, D.R. Flow in Networks. Princeton University Press, Princeton, N.J., 1962.
	13	GOTTLIEB, A. The NYU ultracomputer-designing an MIMD shared-memory parallel computer. IEEE Trans. Comp. C-32 (1983), 175-189.
	14	HATAY, L. Bipartite matching: A computational invesngation of parallel algorithms. Department of Operations Research, Southern Methodist University, Dallas, Tex., 1987.
	15	R. Jonker , A. Volgenant, A shortest augmenting path algorithm for dense and sparse linear assignment problems, Computing, v.38 n.4, p.325-340, March 1987 [doi>10.1007/BF02278710]
	16	KEMPA, D., KENNINGTON, J., AND ZAKI, H. Performance characteristics of the Jacobi and Gauss-Seidel versions of the auction algorithm on the Alliant FX18. Report OR-89-008, Mechanical and Industrial Engineering, University of Illinois at Urbana-Champaign, Urbana, Ill., 1989.
	17	KENNINGTON, J. AND WANG, Z. Solving dense assignment problems on a shared memory multiprocessor, Technical Report 88-OR-16, Department of Operations Research, Southern Methodist University, Dallas, Tex., October 1988.
	18	G. A. P. Kindervater , J. K. Lenstra, Parallel computing in combinatorial optimization, Annals of Operations Research, v.14 n.1-4, p.245-289, June 1988 [doi>10.1007/BF02186483]
	19	KUHN, N.W. The Hungarian method for the assignment problem. Nav. Res. Log. Quart. 2 (1955), 83-97.
	20	LAWt,ER. E. L. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York, 1976.
	21	MARTELLO, S. AND TOTH, P. Linear assignment problems. Ann. Dis. Math. 31 (1987), 259-282.
	22	MCGINNES, L. F. Implementation and testing of a primal-dual algorithm for the assignment problem. Op. Res. 31 (1983), 277-291.
	23	MILLER, D. L. AND PEKNY, J.F. Results from a parallel branch and bound algorithm for solving large asymmetric traveling salesman problems. Op. Res. Lett. 8 (1989), 129-135.
	24	MILLER, D. n., PEKNY, J. F., AND THOMPSON, G. L. Solution of large dense transportation problems using a parallel primal method, MSRR No. 546. Carnegie Mellon University, Pattsburgh, Pa., 1988.
	25	PEKNY, J. F., AND MILLER, D. L. A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems. Report 05-27-88, Engineering Design Research Center, Carnegie Mellon Universlty, Pittsburgh, Pa., 1988.
	26	Randall Rettberg , Robert Thomas, Contention is no obstacle to shared-memory multiprocessing, Communications of the ACM, v.29 n.12, p.1202-1212, Dec. 1986 [doi>10.1145/7902.7905]
	27	TAKIAN, R.E. Data Structures and Network Algorithms. CBMS Regaonal Conference Series No. 44, SIAM, New York, 1983.
	28	TOMIZAWA, N. On some techniques useful for the solution of transportauon network problems. Networks 1 (1971), 173-194.

CITED BY 5

	Richard J. Anderson , João C. Setubal, On the parallel implementation of Goldberg's maximum flow algorithm, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.168-177, June 29-July 01, 1992, San Diego, California, United States
	Robert L. Popp , Krishna R. Pattipati , Yaakov Bar-Shalom , Reda A. Ammar, Shared-Memory Parallelization of the Data Association Problem in Multitarget Tracking, IEEE Transactions on Parallel and Distributed Systems, v.8 n.10, p.993-1005, October 1997
	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
	Libor Buš , Pavel Tvrdík, Towards auction algorithms for large dense assignment problems, Computational Optimization and Applications, v.43 n.3, p.411-436, July 2009
	Mesut Yavuz , Suleyman Tufekci, Dynamic programming solution to the batching problem in just-in-time flow-shops, Computers and Industrial Engineering, v.51 n.3, p.416-432, November, 2006

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.1 NUMERICAL ANALYSIS
G.1.0 General
Subjects: Parallel algorithms

Additional Classification:
C. Computer Systems Organization
C.1 PROCESSOR ARCHITECTURES
C.1.2 Multiple Data Stream Architectures (Multiprocessors)
Subjects: Parallel processors**

F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.1 Numerical Algorithms and Problems
Subjects: Computations on matrices

G. Mathematics of Computing
G.1 NUMERICAL ANALYSIS
G.1.3 Numerical Linear Algebra
Subjects: Sparse, structured, and very large systems (direct and iterative methods)
G.1.6 Optimization
Subjects: Linear programming
G.2 DISCRETE MATHEMATICS
G.2.1 Combinatorics
G.2.2 Graph Theory

I. Computing Methodologies
I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
I.1.2 Algorithms
Subjects: Analysis of algorithms

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
assignment, matching, shortest augmenting paths, traveling salesman problem

REVIEW

"William Fennell Smyth : Reviewer"

The assignment problem (AP) seeks to minimize the cost of assigning n people to n tasks, where each assignment has a fixed cost. It can be modeled as the problem more...

Collaborative Colleagues:

Egon Balas: colleagues

Donald Miller: colleagues

Joseph Pekny: colleagues

Paolo Toth: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player