A continuous \(d\)-step conjecture for polytopes

DOI10.1007/s00454-008-9096-4zbMath1168.52009OpenAlexW2115900859WikidataQ122919700 ScholiaQ122919700MaRDI QIDQ1017920

Tamás Terlaky, Antoine Deza, Yuriy Zinchenko

Publication date: 13 May 2009

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-008-9096-4

zbMATH Keywords

polytopescurvaturediametercentral pathHirsch conjecture\(d\)-step conjecture

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Related Items

An analogue of the Klee-Walkup result for sonnevend's curvature of the central path, Obstructions to weak decomposability for simplicial polytopes, Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, A \(d\)-step approach to the maximum number of distinct squares and runs in strings, Bannai et al. method proves the \(d\)-step conjecture for strings, The central curve in linear programming

Cites Work

• Unnamed Item
• Unnamed Item
• Polytopes and arrangements: diameter and curvature
• On the complexity of following the central path of linear programs by linear extrapolation. II
• Many polytopes meeting the conjectured Hirsch bound
• More polytopes meeting the conjectured Hirsch bound
• On the curvature of the central path of linear programming theory
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• A Mathematical View of Interior-Point Methods in Convex Optimization
• Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Lectures on Polytopes
• Interior Point Methods for Linear Optimization