TY - JOUR

T1 - On the generality of the greedy algorithm for solving matroid base problems

AU - Turner, Lara

AU - Ehrgott, Matthias

AU - Hamacher, Horst W.

PY - 2015/11/20

Y1 - 2015/11/20

N2 - It is well known that the greedy algorithm solves matroid base problems for all linear cost functions and is, in fact, correct if and only if the underlying combinatorial structure of the problem is a matroid. Moreover, the algorithm can be applied to problems with sum, bottleneck, algebraic sum or k-sum objective functions.In this paper, we address matroid base problems with a more general–“universal”–objective function which contains the previous ones as special cases. This universal objective function is of the sum type and associates multiplicative weights with the ordered cost coefficients of the elements of matroid bases such that, by choosing appropriate weights, many different–classical and new–objectives can be modeled. We show that the greedy algorithm is applicable to a larger class of objective functions than commonly known and, as such, it solves universal matroid base problems with non-negative or non-positive weight coefficients. Based on problems with mixed weights and a single (−,+)-sign change in the universal weight vector, we give a characterization of uniform matroids. In case of multiple sign changes, we use partition matroids. For non-uniform matroids, single sign change problems can be reduced to problems in minors obtained by deletion and contraction. Finally, we discuss how special instances of universal bipartite matching and shortest path problems can be tackled by applying greedy algorithms to associated transversal matroids.

AB - It is well known that the greedy algorithm solves matroid base problems for all linear cost functions and is, in fact, correct if and only if the underlying combinatorial structure of the problem is a matroid. Moreover, the algorithm can be applied to problems with sum, bottleneck, algebraic sum or k-sum objective functions.In this paper, we address matroid base problems with a more general–“universal”–objective function which contains the previous ones as special cases. This universal objective function is of the sum type and associates multiplicative weights with the ordered cost coefficients of the elements of matroid bases such that, by choosing appropriate weights, many different–classical and new–objectives can be modeled. We show that the greedy algorithm is applicable to a larger class of objective functions than commonly known and, as such, it solves universal matroid base problems with non-negative or non-positive weight coefficients. Based on problems with mixed weights and a single (−,+)-sign change in the universal weight vector, we give a characterization of uniform matroids. In case of multiple sign changes, we use partition matroids. For non-uniform matroids, single sign change problems can be reduced to problems in minors obtained by deletion and contraction. Finally, we discuss how special instances of universal bipartite matching and shortest path problems can be tackled by applying greedy algorithms to associated transversal matroids.

KW - Combinatorial optimization

KW - Matroids

KW - Universal objective function

KW - Greedy algorithm

KW - Uniform matroids

KW - Minors

KW - Transversal matroids

KW - Bipartite matchings

KW - Shortest paths

U2 - 10.1016/j.dam.2014.08.034

DO - 10.1016/j.dam.2014.08.034

M3 - Journal article

VL - 195

SP - 114

EP - 128

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -