Hardcover ISBN:  9780821865989 
Product Code:  DIMACS/12 
592 pp 
List Price:  $131.00 
MAA Member Price:  $117.90 
AMS Member Price:  $104.80 
Electronic ISBN:  9781470439705 
Product Code:  DIMACS/12.E 
592 pp 
List Price:  $123.00 
MAA Member Price:  $110.70 
AMS Member Price:  $98.40 

Book DetailsDIMACS  Series in Discrete Mathematics and Theoretical Computer ScienceVolume: 12; 1993MSC: Primary 68; 90;
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.
ReadershipResearch mathematicians and computer scientists.

Table of Contents

Chapters

Goldberg’s algorithm for maximum flow in perspective: a computational study

Implementations of the GoldbergTarjan maximum flow algorithm

Implementing a maximum flow algorithm: experiments with dynamic trees

Implementing the pushrelabel method for the maximum flow problem on a connection machine

A case study in algorithm animation: maximum flow algorithms

An empirical study of Min cost flow algorithms

On implementing scaling pushrelabel algorithms for the minimumrelabel algorithms for the minimumcost flow problem

Performance evaluation of the MINET minimum cost netflow solver

A speculative contraction method for minimum cost flows: toward a practical algorithm

An experimental implementation of the dual cancel and tighten algorithm for minimumcost network flow

A fast implementation of a pathfollowing algorithm for maximizing a linear function over a network polytope

An efficient implementation of a network interior point method

On the massively parallel solution of linear network flow problems

Approximating concurrent flow with unit demands and capacities: an implementation

Implementation of a combinatorial multicommodity flow algorithm

Reverse auction algorithms for assignment problems

An approximate dual projective algorithm for solving assignment problems

An implementation of a shortest augmenting path algorithm for the assignment problem

The assignment problem on parallel architectures

An experimental comparison of two maximum cardinality matching programs

Implementing an $O(\sqrt {N}M)$ cardinality matching algorithm

Solving largescale matching problems

appendix A. Electronically available materials

appendix B. Panel discussion highlights


Request Review Copy
 Book Details
 Table of Contents

 Request Review Copy
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.
Research mathematicians and computer scientists.

Chapters

Goldberg’s algorithm for maximum flow in perspective: a computational study

Implementations of the GoldbergTarjan maximum flow algorithm

Implementing a maximum flow algorithm: experiments with dynamic trees

Implementing the pushrelabel method for the maximum flow problem on a connection machine

A case study in algorithm animation: maximum flow algorithms

An empirical study of Min cost flow algorithms

On implementing scaling pushrelabel algorithms for the minimumrelabel algorithms for the minimumcost flow problem

Performance evaluation of the MINET minimum cost netflow solver

A speculative contraction method for minimum cost flows: toward a practical algorithm

An experimental implementation of the dual cancel and tighten algorithm for minimumcost network flow

A fast implementation of a pathfollowing algorithm for maximizing a linear function over a network polytope

An efficient implementation of a network interior point method

On the massively parallel solution of linear network flow problems

Approximating concurrent flow with unit demands and capacities: an implementation

Implementation of a combinatorial multicommodity flow algorithm

Reverse auction algorithms for assignment problems

An approximate dual projective algorithm for solving assignment problems

An implementation of a shortest augmenting path algorithm for the assignment problem

The assignment problem on parallel architectures

An experimental comparison of two maximum cardinality matching programs

Implementing an $O(\sqrt {N}M)$ cardinality matching algorithm

Solving largescale matching problems

appendix A. Electronically available materials

appendix B. Panel discussion highlights