An analogue of the Klee-Walkup result for sonnevend's curvature of the central path

DOI10.1007/S10957-015-0764-2zbMATH Open1370.90140OpenAlexW2182422590MaRDI QIDQ289062FDOQ289062

Tamás Terlaky, Murat Mut

Publication date: 27 May 2016

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10957-015-0764-2

zbMATH Keywords

complexitydiameterinterior-point methodspolytopescurvaturecentral pathlinear optimization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Interior-point methods (90C51) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Cites Work

• A continuous \(d\)-step conjecture for polytopes
• On the complexity of following the central path of linear programs by linear extrapolation. II
• Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
• A primal-dual interior point method whose running time depends only on the constraint matrix
• The \(d\)-step conjecture for polyhedra of dimension \(d<6\)
• Diameter and Curvature: Intriguing Analogies
• Interior Point Methods for Linear Optimization
• Representing the space of linear programs as the Grassmann manifold
• A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms
• Polytopes and arrangements: diameter and curvature

This page was built for publication: An analogue of the Klee-Walkup result for sonnevend's curvature of the central path

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