**DIMACS - Series in Discrete Mathematics and Theoretical Computer Science**

Volume: 12;
1993;
592 pp;
Hardcover

MSC: Primary 68; 90;

**Print ISBN: 978-0-8218-6598-9
Product Code: DIMACS/12**

List Price: $131.00

AMS Member Price: $104.80

MAA Member Price: $117.90

**Electronic ISBN: 978-1-4704-3970-5
Product Code: DIMACS/12.E**

List Price: $123.00

AMS Member Price: $98.40

MAA Member Price: $110.70

# Network Flows and Matching: First DIMACS Implementation Challenge

Share this page *Edited by *
*David S. Johnson; Catherine C. McGeoch*

A co-publication of the AMS and DIMACS

Interest has grown recently in the application of computational and statistical tools to problems in the analysis of algorithms. In many algorithmic domains worst-case 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 three-day workshop held in October 1991 at DIMACS. This volume contains the revised and refereed versions of twenty-two of the papers presented at the workshop, along with supplemental material about the Challenge and the Workshop.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).

#### Readership

Research mathematicians and computer scientists.

# Table of Contents

## Network Flows and Matching: First DIMACS Implementation Challenge

- Cover Cover11
- Title page iii4
- Contents v6
- Foreword ix10
- Preface xi12
- Goldberg’s algorithm for maximum flow in perspective: a computational study 116
- Implementations of the Goldberg-Tarjan maximum flow algorithm 1934
- Implementing a maximum flow algorithm: experiments with dynamic trees 4358
- Implementing the push-relabel method for the maximum flow problem on a connection machine 6580
- A case study in algorithm animation: maximum flow algorithms 97112
- An empirical study of Min cost flow algorithms 119134
- On implementing scaling push-relabel algorithms for the minimum-relabel algorithms for the minimum-cost flow problem 157172
- Performance evaluation of the MINET minimum cost netflow solver 199214
- A speculative contraction method for minimum cost flows: toward a practical algorithm 219234
- An experimental implementation of the dual cancel and tighten algorithm for minimum-cost network flow 247262
- A fast implementation of a path-following algorithm for maximizing a linear function over a network polytope 267282
- An efficient implementation of a network interior point method 299314
- On the massively parallel solution of linear network flow problems 349364
- Approximating concurrent flow with unit demands and capacities: an implementation 371386
- Implementation of a combinatorial multicommodity flow algorithm 387402
- Reverse auction algorithms for assignment problems 407422
- An approximate dual projective algorithm for solving assignment problems 431446
- An implementation of a shortest augmenting path algorithm for the assignment problem 453468
- The assignment problem on parallel architectures 469484
- An experimental comparison of two maximum cardinality matching programs 519534
- Implementing an 𝑂(√𝑁𝑀) cardinality matching algorithm 539554
- Solving large-scale matching problems 557572
- appendix A. Electronically available materials 577592
- appendix B. Panel discussion highlights 583598
- Back Cover Back Cover1608