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

DOI10.1007/S10957-015-0764-2MaRDI QIDQ289062zbMATH OpenOpenAlexFDO

Authors Murat Mut, Tamás Terlaky

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)

Recommendations

• Central path curvature and iteration-complexity for redundant Klee-Minty cubes
• On the curvature of the central path of linear programming theory
• A continuous d-step conjecture for polytopes
• Diameter and Curvature: Intriguing Analogies
• 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

Cites work

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

Cited in

(1)

• A continuous d-step conjecture for polytopes

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)