Polytopes and arrangements: diameter and curvature

DOI10.1016/j.orl.2007.06.007zbMath1144.52024OpenAlexW2004505953MaRDI QIDQ935228

Tamás Terlaky, Yuriy Zinchenko, Antoine Deza

Publication date: 6 August 2008

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2007.06.007

zbMATH Keywords

arrangementspolytopesdiametercentral pathtotal curvature

Mathematics Subject Classification ID

Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Related Items

An analogue of the Klee-Walkup result for sonnevend's curvature of the central path, Diameter and Curvature: Intriguing Analogies, Log-Barrier Interior Point Methods Are Not Strongly Polynomial, Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, What Tropical Geometry Tells Us about the Complexity of Linear Programming, Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes, The tropical analogue of the Helton-Nie conjecture is true, How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds, The central curve in linear programming, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, A continuous \(d\)-step conjecture for polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Probabilistic analysis of optimization algorithms - some aspects from a practical point of view
• An upper bound for the diameter of a polytope
• 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
• Convex Polytopes
• NEWTON FLOW AND INTERIOR POINT METHODS IN LINEAR PROGRAMMING
• Interior Point Methods for Linear Optimization