Condition numbers for polyhedra with real number data

DOI10.1016/0167-6377(95)00019-GzbMath0858.90097MaRDI QIDQ1924613

Yinyu Ye, Stephen A. Vavasis

Publication date: 20 October 1996

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

zbMATH Keywords

primal-dual interior point method; condition-based complexity; feasible point inside a polyhedron; homogeneous linear constraints

Mathematics Subject Classification ID

52B12: Special polytopes (linear programming, centrally symmetric, etc.)

90C05: Linear programming

Related Items

Probabilistic analysis of condition numbers for linear programming, A primal-dual symmetric relaxation for homogeneous conic systems, On strata of degenerate polyhedral cones. I: Condition and distance to strata, On the condition numbers for polyhedra in Karmarkar's form, A primal-dual interior point method whose running time depends only on the constraint matrix, A note on properties of condition numbers, Linear programming, complexity theory and elementary functional analysis, Solving linear programs with finite precision. II: Algorithms

Cites Work

• A new polynomial-time algorithm for linear programming
• On bounds for scaled projections and pseudoinverses
• On scaled projections and pseudoinverses
• Modified barrier functions (theory and methods)
• An accelerated interior point method whose running time depends only on A (extended abstract)
• Simple computable bounds for solutions of linear complementarity problems and linear programs
• Error Bound and Convergence Analysis of Matrix Splitting Algorithms for the Affine Variational Inequality Problem
• Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
• Stable Numerical Algorithms for Equilibrium Systems
• A Dantzig-Wolfe-Like Variant of Karmarkar's Interior-Point Linear Programming Algorithm