On Simplex Pivoting Rules and Complexity Theory

DOI10.1007/978-3-319-07557-0_2zbMath1418.90145arXiv1404.3320OpenAlexW1852734164MaRDI QIDQ5418981

Ilan Adler, Aviad Rubinstein, Christos H. Papadimitriou

Publication date: 2 June 2014

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitylinear programmingsimplex method

Mathematics Subject Classification ID

Linear programming (90C05) Extreme-point and pivoting methods (90C49)

Related Items (10)

Complexity of Single-Swap Heuristics for Metric Facility Location and Related Problems ⋮ Monotone diameter of bisubmodular polyhedra ⋮ The Polyhedral Geometry of Pivot Rules and Monotone Paths ⋮ Inapproximability of shortest paths on perfect matching polytopes ⋮ Unnamed Item ⋮ Computing Kitahara-Mizuno's bound on the number of basic feasible solutions generated with the simplex algorithm ⋮ Monotone paths in geometric triangulations ⋮ On the Length of Monotone Paths in Polyhedra ⋮ Green scheduling, flows and matchings ⋮ Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization

This page was built for publication: On Simplex Pivoting Rules and Complexity Theory