Simplex method and groups generated by reflections

DOI10.1007/BF00049569MaRDI QIDQ2639965zbMATH OpenFDO

Authors L. Faybusovich

Publication date 1990

Published in Acta Applicandae Mathematicae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00049569

zbMATH Keywords

Bruhat orderingconvex hullsCoxeter groupsorbits of Weyl groupspolyhedrapresentationssimplex-methodsorting problemstrajectories

Mathematics Subject Classification ID

Generators, relations, and presentations of groups (20F05) Reflection and Coxeter groups (group-theoretic aspects) (20F55) Convex programming (90C25) Nonlinear programming (90C30)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 1857822
• Linear programming, the simplex algorithm and simple polytopes
• Algorithms for symmetric groups of simplexes
• Simplex-like trajectories on quasi-polyhedral sets.
• The generalized simplex method

Cites work

• A new polynomial-time algorithm for linear programming
• Combinatorial geometries and torus strata on homogeneous compact manifolds
• Geometry and combinatorics of groups generated by reflections
• scientific article; zbMATH DE number 3889273 (Why is no real title available?)
• scientific article; zbMATH DE number 3954641 (Why is no real title available?)
• scientific article; zbMATH DE number 3661606 (Why is no real title available?)
• scientific article; zbMATH DE number 3759173 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3297198 (Why is no real title available?)
• On the efficiency of algorithms of analysis
• Some characterizations of Coxeter groups
• The simplex method in coordinate-free formulation

Cited in

(3)

• Hamiltonian structure of dynamical systems which solve linear programming problems
• scientific article; zbMATH DE number 4160279 (Why is no real title available?)
• Euclidean simplices generating discrete reflection groups

This page was built for publication: Simplex method and groups generated by reflections

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2639965)