DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME TWELVE
TITLE: "NETWORK FLOWS AND MATCHING"
EDITORS: David S. Johnson, Catherine C. McGeoch
Published by the American Mathematical Society


Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.



PREFACE


In recent years there has been growing interest 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 useful knowledge where purely analytical methods fail. Moreover, experiments can provide new insights into algorithmic mechanisms and therefore motivate and guide deeper analytical results. Despite the potential value of the experimental approach, however, there has not been a strong experimental tradition in the field of algorithm analysis.

The DIMACS Implementation Challenge was organized for the purpose of encouraging more work in this area. Sponsored by DIMACS, the Challenge specifically encouraged experimental work in the area of network flows and matchings. Participants at sites in the United States, Europe, and Japan undertook projects during November 1990-August 1991 to test and evaluate algorithms for these problems. The Challenge culminated in a three-day workshop, held October 14-16, 1991, at the DIMACS Center at Rutgers University. This Proceedings contains revised and refereed versions of 22 of the papers presented at the Workshop, along with supplemental material about the Challenge and the Workshop.

One goal of the Challenge was to promote the active interchange of information and sharing of test data among participants. A repository of test instances, sample codes, and even draft papers was maintained at DIMACS, and made electronically available to all participants. Extended abstracts of the workshop papers were circulated before the workshop, and authors were given several months after the workshop to continue their experiments before the Proceedings submissions were due. These submissions were then refereed. In most cases the papers were then substantially revised in response to requests for more experimental data and more detailed explanations of the algorithmic issues involved. The papers are now in final form (although in several cases authors have continued their research and will be writing follow-up papers).

As a result of the cooperative approach taken by the authors and the long gestation period for their papers, this Proceedings should prove more informative than would a random collection of experimental papers on the same topic. Many papers report results on the same classes of instances, and calibrate the speed of their computers using the same set of benchmark tests. Many authors cite each other and make use of lessons learned by the other participants (and, in a few cases, point out the existence of contradictory results that had to be left for future studies to resolve). Thus readers will have an easier task of comparing results and drawing their own conclusions.

The papers are divided into five groups, according to the algorithmic problems they address. The first group of five papers concerns the maximum network flow problem. All touch on the recent push/relabel approach of Goldberg and Tarjan, which workshop participants agreed is the method of choice for practically all instance classes. Anderson and Setubal implement Goldberg-Tarjan and compare it to many of the well-known algorithms that preceded it. Nguyen and Venkateswaran study the effects of various algorithmic choices one can make in an implementation of Goldberg-Tarjan, and Badics and Boros examine the value of using sophisticated data structures in implementing the algorithm (and an alternative algorithm due to Cheriyan and Hagerup). Alizadeh and Goldberg report on experiments in which the Goldberg-Tarjan algorithm is implemented on a massively parallel SIMD computer. Finally Shannon, MacCuish, and Johnson report on lessons learned by animating key aspects of the algorithm's inner workings.

The second group of papers concerns the minimum cost network flow problem. Here there was no clear "champion," as is amply demonstrated in a paper by Bland et al., which compares four distinct approaches (a cost scaling algorithm of Bland and Jensen, a relaxation algorithm of Bertsekas, a network simplex code of Grigoriadis, and a scaling push/relabel algorithm of Goldberg and Tarjan). The paper concludes that each algorithm can either win or lose by large amounts, depending on the instance class. The remaining papers in this group focus more on individual algorithms. Goldberg and Kharitonov investigate a variety of heuristic ideas for speeding up the Goldberg-Tarjan approach. Maros reports on experiments applying his own network simplex code to the problem. Two papers, by Joshi, Goldstein, and Vaidya and Resende and Viega, study interior point approaches to the linear programming formulation of the problem. Two other papers, by Fujishige et al. and by McCormick and Liu, examine some new algorithmic ideas in the context of the graph-theoretic formulation of the problem. The final paper in this group, by Neilsen and Zenios, reports on experiments comparing implementations of a relaxation algorithm and a new algorithm of the authors on a massively parallel machine.

The third group of papers considers the multicommodity flow problem. There has recently been much interesting theoretical work on combinatorial approximation schemes, which by settling for merely getting close to optimal, offer the possibility of running much faster than traditional optimization approaches (such as the simplex algorithm). Papers by Borger, Kang, and Klein and by Leong, Shor, and Stein report on experiments with these theoretically interesting algorithms. Their results suggest that one needs to sacrifice very little in terms of accuracy to obtain impressive speedups, assuming the number of commodities is large.

The fourth group of papers deals with the assignment problem, where again the algorithm of choice may depend heavily on the type of instance under consideration. Castanon considers algorithmic methods for fine-tuning the auction approach to the problem. Hao and Kocur study a new implementation of an algorithm based on shortest augmenting paths. Ramikrishnan, Karmarkar, and Kamath report on extensive tests with a mild specialization of their "approximate dual projective" interior point method for linear programming. Brady et al. look at parallel implementations of several assignment algorithms, and in particular, implementations of the auction algorithm on a variety of parallel architectures.

The fifth and final group of papers considers general graph matching. For the unweighted case, an algorithm of Micali and Vazirani, long viewed as the theoretical champion, had never been seriously studied from an experimental point of view. Papers by Crocker and by Mattingly and Ritchey present


TABLE OF CONTENTS




Foreword							    ix

Preface								
	D.S. Johnson and C.C. McGeoch			            xi

Goldberg's Algorithm for Maximum Flow in Perspective:
	A Computational Study
		R.J. Anderson and J.C. Setubal			     1

Implementations of the Goldberg-Tarjan Maximum Flow
	Algorithm
		Q.C. Nguyen and V. Venkateswaran                    19

Implementing a Maximum Flow Algorithm: Experiments with
	Dynamic Trees
		T. Badics and E. Boros				    43

Implementing the Push-Relabel Method for the Maximum Flow
	Problem on a Connection Machine
		F. Alizadeth and A.V. Goldberg			    65


A Case Study in Algorithm Animation: Maximum Flow Algorithms
	G.E. Shannon, J. MacCuish, and E. Johnson		    97


An Empirical Study of Min Cost Flow Algorithms for the
	Minimum-Cost Flow Problem
		R.G. Bland, J. Cheriyan, D.L. Jensen, and 
			L. Ladanyi				   119


On Implementing Scaling Push-Relabel Algorithms for the 
	Minimum-Cost Flow Problem
		A.V. Goldberg and M. Kharitanov			   157

Performance Evaluation of the MINET Minimum Cost Netflow 
	Solver
		I. Maros					   199


A Speculative Contraction Method for Minimum Cost Flows:
	Toward a Practical Algorithm
		S. Fujishige, K. Iwano, J. Nakano, and S. 
			Tezuka					   219

An Experimental Implementation of the Dual Cancel and Tighten 
	Algorithm for Minimum-Cost Network Flow
		S.T. McCormick and L. Liu			   247

A Fast Implementation of a Path-Following Algorithm for 
	Maximizing a Linear Function over a Network Polytope
		A. Joshi, A.S. Goldstein, and P.M. Vaidya	   267

An Efficient Implementation of a Network Interior Point Method
	M.G.C. Resende and G. Veiga				   299

On the Massively Parallel Solution of Linear Network Flow Problems
	S. Neilsen and S. Zenios				   349

Approximating Concurrent Flow with Unit Demands and Capacities:
	An Implementation
		J.M. Borger, T.S. Kang, and P.N. Klein		   371

Implementation of a Combinatorial Multicommodity Flow Algorithm
	T. Leong, P.W. Shor, and C.Stein			   387

Reverse Auction Algorithms for Assignment Problems
	D.A. Castanon						   407

An Approximate Dual Projective Algorithm for Solving Assignment 
	Problems
		K.G. Ramakrishnan, N.K. Karmarkar, and 
			A.P. Kamath				   431

An Implementation of a Shortest Augmenting Path Algorithm for 
	the Assignment Problem
		J. Hao and G. Kocur				   453

The Assignment Problem on Parallel Architectures
	M. Brady, K.K. Jung, H.T. Nguyen, R. Raghavan, and
		R. Subramonian					   469

An Experimental Comparison of Two Maximum Cardinality 
	Matching Programs
		S.T. Crocker					   519

Implementing on O(/NM) Cardinality Matching Algorithm
	R.B. Mattingly and N.P. Ritchey				   539

Solving Large-Scale Matching Problems
	D. Applegate and W. Cook				   557

Appendix A: Electronically Available Materials
	C.C. McGeoch						   577

Appendix B: Panel Discussion Highlights
	D.S. Johnson						   583


Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.