Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.dam.2014.08.034 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Combinatorial optimization,Matroids,Universal objective function,Greedy algorithm,Uniform matroids,Minors,Transversal matroids,Bipartite matchings,Shortest paths | Matroid,Discrete mathematics,Combinatorics,Shortest path problem,Oriented matroid,Matroid partitioning,Greedy algorithm,Combinatorial optimization,Graphic matroid,Weighted matroid,Mathematics | Journal |
Volume | Issue | ISSN |
195 | C | 0166-218X |
Citations | PageRank | References |
0 | 0.34 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lara Turner | 1 | 7 | 1.86 |
| Matthias Ehrgott | 2 | 923 | 60.59 |
| Horst W. Hamacher | 3 | 562 | 57.39 |