The greedy algorithm and Coxeter matroids (Q1575099)

Given a pair \(M= (X,{\mathcal I})\) consisting of a finite set \(X\) and a non-empty collection \({\mathcal I}\) of subsets of \(X\) together with a function \(\phi:X \to {\mathbb R}\), a natural combinatorial optimization problem is to find a set in \(\mathcal I\) that has greatest total weight. In case \(\phi\) is positive, it is well known this can be solved using a greedy algorithm in case \(M\) is a matroid. In this paper it is shown that a greedy algorithm also provides a solution to an optimization problem that can be naturally associated to Coxeter matroids. This is shown to generalize the above result for matroids, which are special examples of Coxeter matroids. The proof of the main result has an important consequence for Coxeter matroids in that it provides the notions of bases and independent sets for these objects. As an application of the main result a greedy algorithm is given that is shown to solve the \(L\)-assignment problem in case \(L\) is a Coxeter matroid.