Probabilistic analysis of condition numbers for linear programming

DOI10.1023/A:1015460004163zbMath1041.90028OpenAlexW1549624355WikidataQ57733265 ScholiaQ57733265MaRDI QIDQ700762

Felipe Cucker, Dennis Cheung

Publication date: 8 October 2002

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

Full work available at URL: https://doi.org/10.1023/a:1015460004163

zbMATH Keywords

linear programmingprobabilistic analysis of algorithmscondition numbers

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Sensitivity, stability, parametric optimization (90C31) Linear programming (90C05)

Related Items (6)

Smoothed analysis of complex conic condition numbers ⋮ Smoothed analysis of condition numbers and complexity implications for linear programming ⋮ Computational complexity of kernel-based density-ratio estimation: a condition number analysis ⋮ Robust smoothed analysis of a condition number for linear programming ⋮ Coverage processes on spheres and condition numbers for linear programming ⋮ Metric regularity of semi-infinite constraint systems

Cites Work

• Unnamed Item
• Some perturbation theory for linear programming
• A primal-dual interior point method whose running time depends only on the constraint matrix
• On the complexity of linear programming under finite precision arithmetic
• Linear programming, complexity theory and elementary functional analysis
• Condition numbers for polyhedra with real number data
• Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
• A Primal-Dual Algorithm for Solving Polyhedral Conic Systems with a Finite-Precision Machine
• Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
• A new condition number for linear programming

This page was built for publication: Probabilistic analysis of condition numbers for linear programming