The greedy algorithm and Coxeter matroids

Vince, A.

Journal of Algebraic Combinatorics, Tome 11 (2000) no. 2, pp. 155-178.

Résumé

Summary: 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 $\mathbb E$ mathbbE , and let $f _{ x, h} ( w)$ = á $w$ x, h ñ $for$ x, h Ĩ $\mathbb E, w$ Ĩ $W$. f_$\xi ,\eta $ (w) = left$\langle $w$\xi ,\eta $ right$\rangle $text for $\xi , \eta \in $mathbbE,w $\in W$. The L-assignment problem is to minimize the function $f _{ x, h}$ f_$\xi ,\eta $ on a given subset L Í $\subseteq W$.

Détail

Keywords: greedy algorithm, Coxeter group, matroid, Bruhat order