𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A shortest augmenting path method for solving minimal perfect matching problems

✍ Scribed by Ulrich Derigs

Publisher
John Wiley and Sons
Year
1981
Tongue
English
Weight
551 KB
Volume
11
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An efficient procedure for solving minimum weight perfect matching problems is presented. Starting from the empty matching the optimal matching is constructed by successively augmenting along shortest augmenting paths. Such paths can be determined via a special labeling technique. The algorithm is motivated by purely combinatorially natured optimality criteria using the concept of admissible transformations of the cost coefficients. We report on some experience with computer implementations of two different versions of this method and an implementation of Edmonds' BLOSSOM‐algorithm which makes use of Lawler's labeling technique. Though all three methods are comparable with respect to computational complexity the results indicate that the shortest augmenting path method is superior with respect to running time and that even larger problems may be solved in a reasonable amount of time.

πŸ“œ SIMILAR VOLUMES

A Modified Simplex Method for Solving 1-
A Modified Simplex Method for Solving 1-Norm Minimization Problem in Model Predictive Control
✍ Yash P. Gupta πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 226 KB

## Abstract Since the simplex method requires the polyhedron to be in the positive domain, the 1‐norm minimization problems are formulated by substantially increasing the size of the LP problems. This paper presents a simple modification that enables the simplex method to be directly applicable to

Variations on a cutting plane method for
Variations on a cutting plane method for solving concave minimization problems with linear constraints
✍ A. Victor Cabot πŸ“‚ Article πŸ“… 1974 πŸ› John Wiley and Sons 🌐 English βš– 534 KB

## Abstract A cutting plane method for solving concave minimization problems with linear constraints has been advanced by Tui. The principle behind this cutting plane has been applied to integer programming by Balas, Young, Glover, and others under the name of convexity cuts. This paper relates th