Title
Implementing Weighted b-Matching Algorithms:
Insights from a Computational Study
Authors
-
Publication
extended abstract in Proceedings of the Workshop on
Algorithm Engineering and Experimentation
(ALENEX99), Baltimore, Maryland, USA,
Lecture Notes in Computer Science, vol. 1619, pp. 18-36,
Springer-Verlag
Source
-
Classification
-
| MSC: |
| primary: | 90C27 | Combinatorial optimization |
| secondary: | 90C35 | Programming involving graphs or networks |
Keywords
-
weighted perfect b-matching, blossom algorithm, experimental study
-
-
We present an experimental study of an implementation of
weighted perfect b-matching based on Pulleyblank's algorithm (1973).
Although this problem is well-understood in theory and efficient
algorithms are known, only little experience with implementations is
available. In this paper several algorithmic variants are compared
on synthetic and application problem data of very sparse graphs.
This study was motivated by the practical
need for an efficient b-matching solver for an industrial application,
namely as a subroutine in our approach to a mesh refinement problem in
computer-aided design (CAD).
Linear regression and operation counting is used to analyze code variants.
The experiments indicate that a fractional jump-start should be used, a
priority queue within the dual update helps, scaling of b-values
is not necessary, whereas a delayed blossom shrinking heuristic
significantly improves running times only for graphs with average
degree two. The fastest variant of our implementation appears to
be highly superior to a code by Miller and Pekny (1995).
