Network Flows and Matching
Challenge Workshop
Published on 30. October 1993
Book
Hardback
592 pages
978-0-8218-6598-9 (ISBN)
Description
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.
More details
Series
Language
English
Place of publication
Providence
United States
Target group
Professional and scholarly
Illustrations
Illustrations
Weight
1276 gr
ISBN-13
978-0-8218-6598-9 (9780821865989)
Copyright in bibliographic data is held by Nielsen Book Services Limited or its licensors: all rights reserved.
Schweitzer Classification
Content
Goldberg's algorithm for maximum flow in perspective: A computational study by R. J. Anderson and J. C. Setubal Implementations of the Goldberg-Tarjan maximum flow algorithm by Q. C. Nguyen and V. Venkateswaran Implementing a maximum flow algorithm: Experiments with dynamic trees by T. Badics and E. Boros Implementing the push-relabel method for the maximum flow problem on a connection machine by F. Alizadeh and A. V. Goldberg A case study in algorithm animation: Maximum flow algorithms by G. E. Shannon, J. MacCuish, and E. Johnson An empirical study of min cost flow algorithms by R. G. Bland, J. Cheriyan, D. L. Jensen, and L. Ladanyi On implementing scaling push-relabel algorithms for the minimum-cost flow problem by A. V. Goldberg and M. Kharitanov Performance evaluation of the MINET minimum cost netflow solver by I. Maros A speculative contraction method for minimum cost flows: Toward a practical algorithm by S. Fujishige, K. Iwano, J. Nakano, and S. Tezuka An experimental implementation of the dual cancel and tighten algorithm for minimum-cost network flow by S. T. McCormick and L. Liu A fast implementation of a path-following algorithm for maximizing a linear function over a network polytope by A. Joshi, A. S. Goldstein, and P. M. Vaidya An efficient implementation of a network interior point method by M. G. C. Resende and G. Veiga On the massively parallel solution of linear network flow problems by S. Neilsen and S. Zenios Approximating concurrent flow with unit demands and capacities: An implementation by J. M. Borger, T. S. Kang, and P. N. Klein Implementation of a combinatorial multicommodity flow algorithm by T. Leong, P. W. Shor, and C. Stein Reverse auction algorithms for assignment problems by D. A. Castanon An approximate dual projective algorithm for solving assignment problems by K. G. Ramakrishnan, N. K. Karmarkar, and A. P. Kamath An implementation of a shortest augmenting path algorithm for the assignment problem by J. Hao and G. Kocur The assignment problem on parallel architectures by M. Brady, K. K. Jung, H. T. Nguyen, R. Raghavan, and R. Subramonian An experimental comparison of two maximum cardinality matching programs by S. T. Crocker Implementing an $O(\sqrt {N}M)$ cardinality matching algorithm by R. B. Mattingly and N. P. Richey Solving large-scale matching problems by D. Applegate and W. Cook Appendix A: Electronically available materials by C. C. McGeoch Appendix B: Panel discussion highlights by D. S. Johnson.