Simplex method and groups generated by reflections (Q2639965)

The class of polyhedra arising as convex hulls of orbits of Weyl groups is considered. A detailed description of the simplex-method for this class is given. It is shown that there exists a one-to-one correspondence between trajectories of the simplex-method from a particular extreme point and reduced presentations of the related element of the Weyl group. Relationships between Bruhat ordering and sorting problems are studied. Necessary results from the theory of Coxeter groups are given with complete proofs.