Admissible transformations and their applications to matching problems

For special combinatorial optimization problems different kind of objective functions as for instance the classical sum objective or the bottleneck objective are of practical interest. Mostly these objective functions are treated separately and independently. The introduction of an “algebraic objective function” the cost coefficients of which are elements of an ordered commutative semigroup allows a unified treatment. For standard problems like shortest path, matching and matroid intersection problems this approach has led to efficient algorithms for a broad class of objective functions. One specific type of algorithm is based on transformations of the cost coefficients and on a purely combinatorial motivated optimality criterion. We will introduce this principle of “admissible transformations” for the general combinatorial optimization problem with algebraic objective. Then we demonstrate how this general principle combined with some problem specific combinatorial observations leads to efficient and transparent algorithms for the problem of finding an optimal perfect matching.