The Greedy Algorithm and Coxeter Matroids

The notion of matroid has been generalized to Coxeter matroid by Gelfand and Serganova. To each pair (W, P) consisting of a finite irreducible Coxeter group W and parabolic subgroup P is associated a collection of objects called Coxeter matroids. The (ordinary) matroids are a special case, the case W = A (isomorphic to the symmetric group Sym_{_n+1}) and P a maximal parabolic subgroup. The main result of this paper is that for Coxeter matroids, just as for ordinary matroids, the greedy algorithm provides a solution to a naturally associated combinatorial optimization problem. Indeed, in many important cases, Coxeter matroids are characterized by this property. This result generalizes the classical Rado-Edmonds and Gale theorems.A corollary of our theorem is that, for Coxeter matroids L, the greedy algorithm solves the L-assignment problem. Let W be a finite group acting as linear transformations on a Euclidean space , and let The L-assignment problem is to minimize the function on a given subset L W.An important tool in proving the greedy result is a bijection between the set W/P of left cosets and a concrete collection A of tuples of subsets of a certain partially ordered set. If a pair of elements of W are related in the Bruhat order, then the corresponding elements of A are related in the Gale (greedy) order. Indeed, in many important cases, the Bruhat order on W is isomorphic to the Gale order on A. This bijection has an important implication for Coxeter matroids. It provides bases and independent sets for a Coxeter matroid, these notions not being inherent in the definition.