Improved complexity results on solving real-number linear feasibility problems
From MaRDI portal
Publication:2490340
DOI10.1007/s10107-005-0610-7zbMath1134.90554OpenAlexW2052512547MaRDI QIDQ2490340
Publication date: 2 May 2006
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-005-0610-7
Abstract computational complexity for mathematical programming problems (90C60) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Interior-point methods (90C51)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the finite convergence of interior-point algorithms for linear programming
- A new polynomial-time algorithm for linear programming
- A polynomial-time algorithm, based on Newton's method, for linear programming
- On scaled projections and pseudoinverses
- Interior path following primal-dual algorithms. I: Linear programming
- A polynomial-time algorithm for a class of linear complementarity problems
- On the complexity of following the central path of linear programs by linear extrapolation. II
- A modified layered-step interior-point algorithm for linear programming
- A primal-dual interior point method whose running time depends only on the constraint matrix
- Identifying an optimal basis in linear programming
- Linear programming, complexity theory and elementary functional analysis
- Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
- The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
- Path-Following Methods for Linear Programming
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- A Variant of the Vavasis--Ye Layered-Step Interior-Point Algorithm for Linear Programming
- On Linear Least-Squares Problems with Diagonally Dominant Weight Matrices
- A Dantzig-Wolfe-Like Variant of Karmarkar's Interior-Point Linear Programming Algorithm
- A New Iteration-Complexity Bound for the MTY Predictor-Corrector Algorithm
- Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
