The Polyhedral Geometry of Pivot Rules and Monotone Paths

DOI10.1137/22m1475910zbMath1522.90025arXiv2201.05134MaRDI QIDQ6075416

Raman Sanyal, Jesús A. De Loera, Unnamed Author, Unnamed Author

Publication date: 20 September 2023

Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2201.05134

zbMATH Keywords

linear programmingsimplex methodarborescencesmonotone path polytopespivot rulespermutahedrageometry of pivot rules

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Permutations, words, matrices (05A05) Polyhedra and polytopes; regular figures, division of spaces (51M20)

Related Items

Monotone paths on cross-polytopes, Exact Quantization of Multistage Stochastic Linear Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exponential lower bound for Cunningham's rule
• Relative Stanley-Reisner theory and upper bound theorems for Minkowski sums
• \(S\)-hypersimplices, pulling triangulations, and monotone paths
• Topological obstructions for vertex numbers of Minkowski sums
• The simplex method. A probabilistic analysis
• A generalization of Caratheodory's theorem
• Fiber polytopes
• Piles of cubes, monotone path polytopes, and hyperplane arrangements
• Pivot rules for linear programming: A survey on recent theoretical developments
• A polytope related to empirical distributions, plane trees, parking functions, and the associahedron
• The associahedron and triangulations of the \(n\)-gon
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Reverse search for enumeration
• Fiber polytopes for the projections between cyclic polytopes
• On Friedmann's subexponential lower bound for Zadeh's pivot rule
• On a special class of hyper-permutahedra
• Linear programming. Foundations and extensions.
• \(H\)-spaces from a homotopy point of view
• The simplex algorithm with the pivot rule of maximizing criterion improvement
• The Complexity of the Simplex Method
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
• Permutohedra, Associahedra, and Beyond
• Cellular Strings on Polytopes
• Lectures on Polytopes
• Convex Polytopes
• The Simplex Algorithm Is NP-Mighty
• Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
• A Friendly Smoothed Analysis of the Simplex Method
• A friendly smoothed analysis of the simplex method
• On Simplex Pivoting Rules and Complexity Theory
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• A Class of Convex Bodies
• Combinatorial optimization. Theory and algorithms.
• Extended formulations in combinatorial optimization
• Hypergraphic polytopes: combinatorial properties and antipode
• Enumerative problems for arborescences and monotone paths on polytope graphs
• An effective solution to convex 1-body \(N\)-representability