Condition numbers for polyhedra with real number data

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

Stephen A. Vavasis, Yinyu Ye

Publication date: 20 October 1996

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

zbMATH Keywords

primal-dual interior point methodcondition-based complexityfeasible point inside a polyhedronhomogeneous linear constraints

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05)

Related Items (11)

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 ⋮ A primal-dual symmetric relaxation for homogeneous conic systems ⋮ Rescaling Algorithms for Linear Conic Feasibility ⋮ A condition-based algorithm for solving polyhedral feasibility problems ⋮ Refining the partition for multifold conic optimization problems ⋮ Probabilistic analysis of condition numbers for linear programming ⋮ Solving linear programs with finite precision. II: Algorithms ⋮ On strata of degenerate polyhedral cones. I: Condition and distance to strata ⋮ On the condition numbers for polyhedra in Karmarkar's form

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

This page was built for publication: Condition numbers for polyhedra with real number data