DIMACS: Series in Discrete Mathematics and Theoretical Computer Science 1993; 592 pp; hardcover Volume: 12 ISBN10: 0821865986 ISBN13: 9780821865989 List Price: US$117 Member Price: US$93.60 Order Code: DIMACS/12
 Interest has grown recently in the application of computational and statistical tools to problems in the analysis of algorithms. In many algorithmic domains worstcase bounds are too pessimistic and tractable probabilistic models too unrealistic to provide meaningful predictions of practical algorithmic performance. Experimental approaches can provide knowledge where purely analytical methods fail and can provide insights to motivate and guide deeper analytical results. The DIMACS Implementation Challenge was organized to encourage experimental work in the area of network flows and matchings. Participants at sites in the U.S., Europe, and Japan undertook projects between November 1990 and August 1991 to test and evaluate algorithms for these problems. The Challenge culminated in a threeday workshop held in October 1991 at DIMACS. This volume contains the revised and refereed versions of twentytwo of the papers presented at the workshop, along with supplemental material about the Challenge and the Workshop. Copublished with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 17 were copublished with the Association for Computer Machinery (ACM). Readership Research mathematicians and computer scientists. Table of Contents  R. J. Anderson and J. C. Setubal  Goldberg's algorithm for maximum flow in perspective: A computational study
 Q. C. Nguyen and V. Venkateswaran  Implementations of the GoldbergTarjan maximum flow algorithm
 T. Badics and E. Boros  Implementing a maximum flow algorithm: Experiments with dynamic trees
 F. Alizadeh and A. V. Goldberg  Implementing the pushrelabel method for the maximum flow problem on a connection machine
 G. E. Shannon, J. MacCuish, and E. Johnson  A case study in algorithm animation: Maximum flow algorithms
 R. G. Bland, J. Cheriyan, D. L. Jensen, and L. Ladányi  An empirical study of min cost flow algorithms
 A. V. Goldberg and M. Kharitanov  On implementing scaling pushrelabel algorithms for the minimumcost flow problem
 I. Maros  Performance evaluation of the MINET minimum cost netflow solver
 S. Fujishige, K. Iwano, J. Nakano, and S. Tezuka  A speculative contraction method for minimum cost flows: Toward a practical algorithm
 S. T. McCormick and L. Liu  An experimental implementation of the dual cancel and tighten algorithm for minimumcost network flow
 A. Joshi, A. S. Goldstein, and P. M. Vaidya  A fast implementation of a pathfollowing algorithm for maximizing a linear function over a network polytope
 M. G. C. Resende and G. Veiga  An efficient implementation of a network interior point method
 S. Neilsen and S. Zenios  On the massively parallel solution of linear network flow problems
 J. M. Borger, T. S. Kang, and P. N. Klein  Approximating concurrent flow with unit demands and capacities: An implementation
 T. Leong, P. W. Shor, and C. Stein  Implementation of a combinatorial multicommodity flow algorithm
 D. A. Castañon  Reverse auction algorithms for assignment problems
 K. G. Ramakrishnan, N. K. Karmarkar, and A. P. Kamath  An approximate dual projective algorithm for solving assignment problems
 J. Hao and G. Kocur  An implementation of a shortest augmenting path algorithm for the assignment problem
 M. Brady, K. K. Jung, H. T. Nguyen, R. Raghavan, and R. Subramonian  The assignment problem on parallel architectures
 S. T. Crocker  An experimental comparison of two maximum cardinality matching programs
 R. B. Mattingly and N. P. Richey  Implementing an \(O(\sqrt {N}M)\) cardinality matching algorithm
 D. Applegate and W. Cook  Solving largescale matching problems
 C. C. McGeoch  Appendix A: Electronically available materials
 D. S. Johnson  Appendix B: Panel discussion highlights
