A framework for the greedy algorithm.
Perhaps the best known algorithm in combinatorial optimization is the greedy algorithm. A natural question is for which optimization problems does the greedy algorithm produce an optimal solution? In a sense this question is answered by a classical theorem in matroid theory due to Rado and Edmonds. In the matroid case, the greedy algorithm solves the optimization problem for every linear objective function. There are, however, optimization problems for which the greedy algorithm correctly solves the optimization problem for many--but not all--linear weight functions. Our intention is to put the greedy algorithm into a simple framework that includes such situations. For any pair (S,P) consisting of a finite set S together with a set P of partial orderings of S, we define the concepts of greedy set and admissible function. On a greedy set L  S, the greedy algorithm correctly solves the naturally associated optimization problem for all admissible functions f consists of linear orders, the greedy sets are characterized by this property. A geometric condition sufficient for a set to be greedy is given in terms of a polytope and roots that generalize Lie algebra root systems.
Introduction
This paper concerns a classical algorithm in combinatorial optimization, the greedy
algorithm. The MINIMAL SPANNING TREE problem, for example, is solved by the
greedy algorithm: Given a nite graph G with weights on the edges, nd a spanning
tree of G with minimum total weight. At each step in the greedy algorithm that solves
this problem, there is chosen a set of edges T comprising the partial tree; an edge e of
minimum weight among the edges not in T (the greedy choice) is added to T so long as
contains no cycle.
A greedy algorithm makes a locally optimal choice in the hope that this will lead to
a globally optimal solution. Clearly, greedy algorithms do not always yield the optimal
solution. But for a wide range of important problems the greedy algorithm is quite
powerful; a variety of such applications can be found in standard texts such as those by
Lawler [8] or Papadimitriou and Steiglitz [9]. A natural question, precisely posed below,
is the following. For which optimization problems does the greedy algorithm give the
correct solution. In a sense this question is answered by a classical theorem in matroid
theory due to Rado and Edmonds [4]. In the matroid case, the greedy algorithm always
solves the optimization problem. That is, the greedy algorithm solves the optimization
problem for every linear objective function. There are situations, however, for which
the greedy algorithm works for many - but not all - linear objective functions. A simple
framework for such problems is suggested below.
To make the question precise, consider a set system (S; I) consisting of a nite set
S together with a nonempty collection I of subsets of S, called independent sets, closed
under inclusion. Given a weight function f R, extend this function linearly to
the collection of subsets A  S by dening
a2A
There is a natural combinatorial optimization problem associated with the set system
I).
OPTIMIZATION PROBLEM.
Given a weight function f nd an independent set with the greatest weight.
In the spanning tree problem, S is the set of edges of the graph G and the independent
sets are the acyclic subsets of edges. Minimum and maximum in this problem are
interchanged by negating the weights.
The greedy algorithm for this optimization problem is simply:
GREEDY ALGORITHM
while S 6= ; do
remove from S an element a of largest weight.
I [ fag is independent then
By the theorem of Edmonds and Rado referred to earlier, the following statements
are equivalent for the set system (S; I). Here B denotes the set of bases, a basis being
a maximum independent set.
1. (S; I) is a matroid.
2. The greedy algorithm correctly solves the combinatorial optimization problem
associated with (S; I) for any weight function f
3. Every basis has the same cardinality and, for every linear ordering  on S, there
exists a such that for any A 2 B, if we
with the elements of B and A both in increasing order, then
a This ordering on k-element subsets of X is called the Gale order.
In the spanning tree problem, the acyclic subsets of edges comprise the independent
sets of a matroid. Many well known optimization problems, besides the spanning tree
problem, can be put into the framework of matroids. Texts by Lawler [8] and by
Papadimitriou and Steiglitz [9] contain numerous examples.
Matroids are characterized by the property that the greedy algorithm correctly solves
the optimization problem for any weight function. There are, however, non-matroids
for which the greedy algorithm correctly solves the appropriate optimization problem
for many - but not for every weight function. This is the case for the following, in
order of increased generality: symmetric matroids [2], sympletic matroids [1] and the
Coxeter matroids of Gelfand and Serganova [5, 6, 11]. It is our intention in this paper
to put the greedy algorithm into a simple framework that includes such examples. In
particular, Theorems 4.1 and 4.2 in this paper contain, as a special case, the classical
matroid theorem of Rado and Edmonds stated earlier. In [1] (Theorem 16), Borovik,
Gelfand and White prove that for symplectic matroids the greedy algorithm correctly
solves the optimization problem for all \admissible" functions. This is also a special case
of Theorem 4.1; symplectic matroids are used as an example in Sections 2, 3 and 4 of this
paper. Given a Coxeter system (W; P ) consisting of a nite irreducible Coxeter group
W and maximal parabolic subgroup P , in [11] (Theorem 1) a concrete realization of the
set W=P of left cosets is given as a collection of subsets B of an appropriate partially
ordered set S. Theorem 3 of [11], in part, states that the natural optimization problem
for Coxeter matroids is solved, for all appropriate \admissible" objective functions, by
the greedy algorithm applied to (S; B). This result is again a special case of Theorem 4.1.
The framework in this paper, however, is conceptually simpler than the usual approaches
to Coxeter matroids. The theory of greedoids, developed by Korte and Lovasz [7],
concerns a framework for optimization problems for which the greedy algorithm nds
the optimal for all generalized bottleneck functions. Since our results concern linear
objective functions, they do not subsume results on greedoids. Our results on the
greedy algorithm apply to situations not previously appearing in the literature, for
example the cyclic and bipartite cases mentioned in Sections 3 and 4. Concerning
open avenues of research, it would be interesting to formulate additional optimization
problems, analogous to the minimum spanning tree problem for matroids, to which the
theory is applicable.
The basic notion in this paper is that of a pair (S; P) consisting of a nite set S
together with a set P of partial orderings of S. The notions of greedy set and admissible
function are dened in Section 2 and examples are given in Sections 2 and 3. It is shown
in Section 4 that, for greedy sets, the greedy algorithm correctly solves the naturally
associated optimization problem for all admissible functions. Indeed, when P contains
only linear orders, the greedy sets are characterized by this property. It is also proved in
Section 4 that there is essentially no loss of generality in assuming that P contains only
linear orders. Our results naturally lead to the problem of eectively characterizing
greedy sets. A geometric approach via polytopes and a generalization of Lie algebra
root systems is taken in Section 5. It is proved that if every edge of the polytope of a
collection L is parallel to a root, then L is a greedy set.
Greedy sets and Admissible Functions
A partial ordering  of a set S is a binary relation on S that is re
exive, transitive and
antisymmetric. If, for any a and b in S, either a  b or b  a then the partial ordering is
called a linear ordering of S. The notation a  b will mean that a  b but a 6= b.
Consider a pair (S; P) consisting of a nite set S and a collection P of partial
orderings of S. A subset L  S will be called a greedy set for the pair (S; P) if L has a
maximum for every ordering in P. That is, for every ordering  in P, there is an a 2 L
such that b  a for all b 2 L.
denote the collection of all k-element subsets of S. Each partial order  on
S induces a partial order on S k , namely the Gale order. If A; B 2 S k , then AB in the
Gale order if there are arrangements
of the elements of the two sets such that a i  b i for all i. The set of Gale orderings
induced on S k by the orderings in P will be denoted P k . A greedy set for the pair
will be referred to as a rank k greedy set for (S; P).
A weight function f called compatible with a partial order  on S if
f(a) < f(b) whenever a  b. A weight function f is said to be admissible for (S; P) if f
is compatible with some partial order in P. An admissible weight function f for (S; P)
can be extended to an admissible weight function f dening
a2A
That this function is indeed admissible is the statement of the corollary below. The rst
proposition is obvious from the denitions of greedy set and admissible weight function.
Proposition 2.1 If L  S is a greedy set for (S; P) and f is an admissible weight
function, then f attains a unique maximum on L.
Proposition 2.2 Let S be a partially ordered set and S k the set of all k-element subsets
of S with the Gale order. For any A; B 2 S k we have BA if and only if f(B)  f(A)
for every weight function f compatible with the order on S.
Proof: Assume that BA. Then there are orderings
(b
Conversely assume that it is not the case that BA. We will construct a function
f that is compatible with the order on S but for which f(B) > f(A). For each element
a xag. Now BA in the Gale order if and only if there is
a set of distinct representatives of the sets B a ; a 2 A. Hence there is not such set of
representatives, and, by Philip Hall's theorem on distinct representatives, there must be
a set A 0  A such that g. Now dene
this function we have
It is easy to see that this function f can be perturbed slightly to be compatible with
the order on S and to retain the property that f(B) > f(A).
Remark. By the same reasoning as in the proof above, it is also true that, for any
if and only if f(B) < f(A) for every weight function f
compatible with the order on S.
Corollary 2.3 If f R is admissible for
This paper uses notation that is common in the literature. In particular, we use [n]
for the set f1; ng of the rst n positive integers. For readability, brackets may be
deleted in denoting a set; for example f2; 4; 6g may be denoted simply 246.
Example 2.4 Matroids are a special case.
let P be the set of all linear orderings of S. Then clearly every
injective weight function f : S ! R is admissible. By denition, a rank k greedy set L
is a collection of k-element subsets of S such that, for every linear ordering of [n], there
is a unique maximum in L in the induced Gale ordering on S k . But this is exactly the
third characterization of matroid given in the introduction. In other words, L is a rank
k greedy set for (S; P) if and only if L is the set of bases of a rank k matroid.
Example 2.5 Symplectic matroids. Let [n] and let
By convention i be the set of all linear orderings  of S with the property
that i  j if and only if j   i  for any i; j 2 S. Equivalently, the pair i and i  appear
symmetrically in the order. For example, with one such order is 2  1   3
. Consequently the admissible weight functions include all injective weights
R such that f(i  for each i 2 [n]. A symmetric matroid of Bouchet
[2] is exactly a rank n greedy set L for the pair (S; P) with the additional property that
for each A 2 L. More generally, the rank k greedy sets, 0  k  n, satisfying
this same property are exactly the symplectic matroids of Borovik, Gelfand and White
[1]. The signicance of the added assumption will be discussed in the next section.
3 The Group Case
Let S be a partially ordered set and G a transitive group of permutations of S. If
denotes the order on S and  2 G, let   denote the order dened by
a   b if  1 a   1 b:
For rank k subsets, the corresponding Gale order will likewise be denoted A  B. This
shifted order will be called the -order. Let be the set of all -orders on S
for  2 G. For example, if with the order 1  2      n, then P is the set of
all orders (1)  (2)      (n) where  2 G. The pair (S; P(G)) is referred to as
the group case.
Although G acts transitively on S, the induced action of G on S k may not be tran-
sitive. There will therefore be situations where attention will be restricted to a single
orbit O k of G acting on S k . The rank k greedy sets of (S; P(G)) will then be restricted
to being contained in a set O k on which G acts transitively.
Example 3.1 Matroids. If with the linear order
and  n is the symmetric group consisting of all permutations of [n], then the greedy
sets for (S; P( n are exactly the ordinary matroids of Example 2.4.
Example 3.2 Symplectic matroids. Let with the linear order
and let G be the hyperoctahedral group of permutations of S generated by all transpositions
of the form (i i  ) and all involutions of the form (i j)(i  j  ). Note that the set
of all k-element sets A with the property that A \ A single orbit of G
acting on S k ; call this orbit O k . Then the greedy sets L  O k for (S; P(G)) are exactly
the symplectic matroids of Example 2.5 above.
Example 3.3 Cyclic case. Let be a poset with the order
and let G be the cyclic group acting on [n] and generated by the cycle (1 2    n). For
example, 3  4  1  2 is a cyclic ordering for 4. It is interesting that, even for
this elementary example, characterization of the collection of greedy sets is evasive. For
example, it is easy to check that the orbit of 652 under the action of the cyclic group C 7
acting on is a greedy set, but the orbit of 652 under the action of C 6 acting on
[6] is not a greedy set. (As noted earlier, the set f6; 5; 2g is denoted simply 652.)
Example 3.4 Bipartite case. Let consist of any linear
order such that either all the unstarred elements precede the starred elements or all the
starred elements precede the unstarred elements. This is the group case where, if [n]
and [n]  are considered as vertex sets of the two parts of a complete bipartite graph
K n;n , then the group is the automorphism group of K n;n .
4 The Greedy Algorithm
As previously, S is a nite set and P a collection of partial orderings of S. The optimization
problem applied to the pair (S; P) is the following.
OPTIMIZATION PROBLEM
Given an admissible weight function f and a set L  S k , nd an element
of L that maximizes the induced weight function f
Given L  S k , call a subset I  S independent with respect to L if I is a subset
of some element of L. The greedy algorithm, precisely as stated in the introduction,
applied to this optimization problem, merely chooses the largest weight element at each
stage subject to the condition that the resulting set is independent with respect to L.
The following result is basic.
Theorem 4.1 Let (S; P) be a pair consisting of a collection P of orderings of the nite
set S. If L  S k is a rank k greedy set, then the greedy algorithm correctly solves the
optimization problem for every admissible weight function f
Proof: Assume that L is a greedy set and that f is compatible with some order, say , in
P. Since L is a greedy set, it contains a unique set A that is maximumwith respect to the
Gale order. We claim that the greedy algorithm selects this set A. Suppose, instead that
B is chosen where BA. Order the sets
that the elements of B appear in the order selected by the greedy algorithm and b i  a i
for 1  i  k. Assume that a
by the compatibility of f , that f(b j ) < f(a j ). But this contradicts the fact that, at this
stage, the greedy algorithm chooses b j .
In the case that P contains only linear orderings of S, the greedy sets are actually
characterized by the property that the greedy algorithm correctly solves the optimization
problem for every admissible weight function. The assumption that P contains only
linear orderings of S is a reasonable one in light of Theorem 4.3 below.
Theorem 4.2 Let P be a set of linear orderings of S and L  S k . Then the greedy
algorithm correctly solves the optimization problem for every admissible weight function
if and only if L is a greedy set.
Proof: In one direction, this result is a corollary of Theorem 4.1. To prove it in the other
direction, assume that L is not a greedy set. Then there exists an order on S, say ,
for which L does not attain a unique maximum. Since  is a linear ordering of S, order
the elements in each set in L in decreasing order. Let A denote the lexicographically
maximum element of L, and let B 6= A be a set in L that is a maximum with respect
to Gale order. According to Proposition 2.2 there exists a weight function compatible
with  such that f(B) > f(A). On the other hand, the greedy algorithm chooses A.
It is desirable to choose P so that there are many admissible weight functions and
many rank k greedy sets. Then the greedy algorithm will correctly solve a large collection
of optimization problems. Unfortunately, these two objectives - many admissible
functions and many greedy sets - are often con
icting. If (S; P) and (S; Q) have the
same collection of admissible functions, but, for each k, each rank k greedy set for (S; P)
is a rank k greedy set for (S; Q), then clearly it is preferable, for algorithmic purposes,
to use (S; Q) rather than (S; P).
Theorem 4.3 For any pair (S; P) there is a pair (P; Q) such that
1. Q contains only linear orders;
2. (S; P) and (S; Q) have the same admissible injective functions; and
3. for each k, each rank k greedy set for (S; P) is also a rank k greedy set for (S; Q).
Proof: Let Q be the collection of all linear extensions of the orders in P. Clearly
condition (1) is satised. Concerning condition (2) assume that weight function f is
admissible for (S; Q). Then f is compatible with some linear ordering  in Q and hence
is also compatible with any ordering in P having  as a linear extension. Therefore
f is admissible for (S; P). Conversely assume that f is admissible for (S; P) and is
injective. Then f is compatible with some ordering  in P. Assume that the elements
of of S are indexed such that f(x 1
by denition, the linear order x 1  x 2      x n is a linear extension of  and f is
compatible with this linear order. Therefore f is admissible for (S; Q).
Concerning condition (3) assume that L is a rank k greedy set for (S; P). To show
that L must also be a greedy set for (S; Q), let  be any linear order in Q. Then  is
a linear extension of some order  in P. Since L is greedy for (S; P), there is a unique
maximum set in L such that, for any
for all i for some ordering of the elements of A and B. Because  is a linear extension
of , it is also true that b i  a i for all i. Therefore A is also the unique maximum with
respect to the Gale order relative to . So L is a greedy set for (S; Q).
Remark. The assumption in condition (2), that the admissible functions be injective,
is not a serious restriction because, for any admissible function f , there is an injective
admissible function that is small perturbation of f .
The following examples are intentionally kept simple in order to illustrate the main
ideas.
Example 4.4 Symplectic matroids. This is a continuation of Example 2.5 of Section
2. Consider the case 3. It is not hard to check that the set
is a rank 2 greedy set. Consider, as an example, the particular function f : [3][[3]  ! R
dened by
This is an admissible function because it is compatible with the ordering 1  2  3
. The greedy algorithm applied to L chooses the set 1  3  whose total
weight is 10, greater than that of any other set in L.
On the other hand, for the function
which is not admissible, the greedy algorithm again chooses the set 1  3  whose total
weight is 7, but the total weight of 12  is 9. The greedy algorithm fails in this case.
(Note that the collection L is not an ordinary matroid on the set [3] [ [3]  .)
Example 4.5 Cyclic case. This is a continuation of Example 3.3 of Section 3.
Consider the case 4, and take the admissible weight function
2:
The set
is a rank 2 greedy set for (S; P). The greedy algorithm chooses 24 whose weight is 6,
greater than the other element of L. On the other hand, for the weight function
which is not admissible, the greedy algorithm fails for L.
Example 4.6 Bipartite case. This is a continuation of Example 3.4 of Section 3.
Consider the case
is a rank 2 greedy set. An admissible function is one for which either f(i) < f(j) for
every unstarred i and starred j or f(i) < f(j) for every starred i and unstarred j. As a
simple example, let
Then f is admissible, and the greedy algorithm chooses 1  2  which has total weight 7
compared to the total weight 3 of 12. On the other hand the function
is not admissible. The greedy algorithm chooses 1  2  which has total weight 6, although
12 has greater total weight 7.
5 Roots and Polytopes
In light of Theorems 4.1 and 4.2, it is important to have an e-cient method to determine
whether a collection L  S k is a greedy set. If (S; P) is such that
of N linear orderings of S, then N may well be exponential as a function of n. If L is
a collection of k-element subsets of S, then it will take no less than exponential time
to check, using the denition, whether L is a greedy set. An alternative procedure is
sought that is polynomial in n and the cardinality of L. In the matroid case, any one of
many cryptomorphic denitions of matroid can be used to do this; that is one of the nice
properties of matroids. For ordinary and symplectic matroids, the associated matroid
polytope [10] furnishes an e-cient procedure to determine whether a set is greedy. For
the general case, we give a geometric approach (Theorem 5.7 and the remarks that follow
using polytopes and roots.
Because of Theorem 4.3, it will be assumed throughout this section that
and P contains only linear orders. Each linear order  in P can be denoted by the
permutation  for which 1  Given the pair (S; P), we will
associate a polytope (L) to each subset L  S k as follows. Let  be the
canonical orthonormal basis for n-dimensional Euclidean space R n . For any k-element
subset A of S, set
Let (L) be the convex hull of the points f-A j A 2 Lg. Notice that (L) lies in the
(n 1)-dimensional hyperplane in R n with equation
Dene a root of (S; P) as a non-zero vector
1.
2.
3. for every  2 P there exists an   2 f1; 1g such that
for each
In particular, note that  i  j is a root of any pair (S; P) for all i 6= j. Our denition
of root of (S; P) is meant as a generalization of a Lie algebra root system. The two
notions coincide for root systems of Coxeter groups. In the group case, we refer to a
root of (S; P(G)) as a root of G. The group acts on the set of roots. The roots in the
following examples are easy to compute.
Example 5.1 For either the symmetric group  n or the alternating group A n acting
on [n], the roots are
Example 5.2 For the cyclic group Z n of Example 3.3 acting on [n], the roots are
f
In other words, +1 and 1 alternate in the vector r. For
example, with the vector (1; 0; is a root while (1; 1; 0; 1; 1) is not.
Example 5.3 For the hyperoctahedral group of Example 3.2 acting on [n] [ [n]  the
roots are
For example, for the vector (1; 1; 0; 0; 1; 1) is a root.
Example 5.4 For the bipartite group of Example 3.4 acting on [n] [ [n]  , let
. The roots are
The idea now is, given a set L, to nd a computationally e-cient algorithm, in
terms of its polytope (L), for deciding whether L is a greedy set. A vector
will be called -admissible for (S; P) if 0 < x 1 < x
x n . A vector that is -admissible for some  2 P will simply be called admissible.
Theorem 5.5 A subset L  S k is a rank k greedy set for (S; P) if and only if, for each
admissible vector v, the linear function f v attains a maximum on (L) at
a unique vertex.
Proof: If
Notice that, for we have, by Proposition 2.2 and the remark
following it, that A  B in the -Gale order if and only if f(A) < f(B) for all positive
weight functions f compatible with   . This is equivalent to
i2B f(i) for
all positive weight functions such that 0 < f(1) < f(2) <    < f(n). But this, in
turn, is the same as f v (- A
vectors
v. Thus the linear function f v attains a maximum on (L) at a unique
vertex for each admissible vector v if and only if there is a unique -Gale maximum in
L for each  2 P. But the latter condition is the denition of greedy set.
Lemma 5.6 Let r be a vector satisfying conditions (1) and (2) in the denition of root.
Then r is a root if and only if r ? contains no admissible vector.
Proof: Assume that orthogonal to some admissible vector
is admissible, there is a  2 P such that 0 < x 1 < x 2 <
We have
1g. Then
Assume, by way of contradiction, that
r is a root. Condition (3) in the denition of root implies (without loss of generality)
that there is a bijection  from A onto B so that (i) > i for all i 2 A. But this implies
that
Conversely, assume that not a root. We use the same notation
A and B as above for some xed  2 P violating condition (3). Without loss of
generality we can ignore the 0 entries in r and assume that A [ [n] and that
A. Dene a bijection  from A to B recursively as follows. Let (1) be the least
element of B. Having dened (i) for i < j, dene (j) as the least element of B
not already in the image of . Let
and r is not a root, C and
are nonempty. A -admissible vector now be chosen so that
arbitrary positive and negative values, respectively.
In particular, a -admissible vector v can be chosen so that hr;
Theorem 5.7 Let P be a collection of linear orderings of a nite set S and let L  S k .
If every edge of (L) is parallel to a root, then L is a greedy set for (S; P).
Proof: Assume that L is not a greedy set. By Theorem 5.5 there exists an admissible
vector such that the linear function f v achieves its maximum on at
least two vertices of (L). Since (L) is convex, f v achieves its maximum on some
edge e of (L). Therefore he; e is not parallel to a root.
Unfortunately the converse of Theorem 5.7 is, in general, false. There exist greedy
sets L for which the polytope (L) has non-root edges. As an example, consider the
cyclic group Z 5 acting on the poset 5g. This is the group case
Example 3.3. If
then L is a greedy set: The (Gale) maximum is 35 for the order 12345; 15 for the order
for the order 34512; 23 for the order 45123; and 34 for the order 51234. It
is easy to check that the segment joining - 12 and - 34 is an edge e of (L) but that
is not a root because condition (3) in the denition fails.
Recall from Section 3 that in the group case it is natural to require that L be
contained in a single orbit O k  S k under the action of G. This is, however, not the
case in the above example; L is not contained in a single orbit of S 2 under the action of
Z 5 . This motivates the following question.
Question 5.8 Let G denote a permutation group acting on S, and let O k be an orbit
of G acting on S k . Is it true that L  O k is a rank k greedy set for (S; P(G)) if and
only if every edge of (L) is parallel to a root of G?
In certain cases the question can be answered in the a-rmative. An edge joining
vertices x and y of a polytope  in R n will be called supporting if it is contained
in a supporting hyperplane of  that is orthogonal to an admissible vector v with
According to Lemma 5.6, an edge of a polytope (L) not parallel to a
root must be orthogonal to some admissible vector; so it is possible for such an edge to
be supporting. Also according to Lemma 5.6, an edge that is parallel to a root cannot be
supporting. A set L  S k is called supporting if each edge of (L) is either supporting
or parallel to a root.
Theorem 5.9 Let P be a collection of linear orderings of a nite set S such that P is
closed under the operation of taking the inverse (reversing order). Assume that L  S k
is supporting. Then L is a greedy set for (S; P) if and only if every edge of (L) is
parallel to a root.
Proof: In one direction the statement follows directly from Theorem 5.7. Conversely,
assume that some edge e of (L) is not parallel to a root. Because L is supporting,
there is an admissible vector v such that e is contained in a supporting hyperplane
of (L) that is orthogonal to v, and the linear function f v
values at the two endpoints of e. This implies that f v (x) attains a maximum on (L)
at both endpoints of the edge e or a minimum at both endpoints of the edge e. By
Theorem 5.5, if f v (x) attains a maximum at both endpoints, then L is not a greedy
set. If f v (x) attains a minimum at both endpoints, say - A and - B , then, as in the proof
of Theorem 5.5, there is a  2 P such that A and B are both minimum in the -Gale
order. But a Gale minimum for  is a Gale maximum for the inverse of , which is also
in P. Hence L is not a greedy set.
Let G be a permutation group acting on S. Then P(G) is closed under the operation
of taking the inverse. Let O k be an orbit under the induced action of G on S k . Sometimes
it is the case that any L  O k is supporting. This is so, for example, if each vector
determined by a point on the boundary of (O k ) is either admissible or orthogonal to
a root. It can be shown that this is the case for ordinary and symplectic matroids. In
general, it is not the case that any L  O k is supporting. Again consider the cyclic
group Z 5 acting on the poset f1; 2; 3; 4; 5g. If
then L lies on one orbit under the action of the cyclic group acting on the set of pairs
but the edge joining - 12 and - 34 in (L) is not a root and
is not supporting. For e to be supporting, there would have to exist an admissible
vector This would imply that either
In both cases, the vertices
lie on dierent sides of the hyperplane containing e and orthogonal to v. So
there does not exist a supporting hyperplane of (L) containing e which is orthogonal
to some admissible vector.



--R

Combinatorics 8
Mathematical Programming 38
Optimal assignments in an ordered set: an application of matroid theory
Matroids and the greedy algorithm
On a general de
Combinatorial geometries and torus strata on homogeneous compact manifolds

Networks and Matroids

A geometric characterization of Coxeter matroids
The greedy algorithm and Coxeter matroids
--TR
Combinatorial optimization: algorithms and complexity
Greedy algorithm and symmetric matroids
Symplectic Matroids
The Greedy Algorithm and Coxeter Matroids
coxeter matroid;greedy algorithm;matroid