Probabilistic analysis of condition numbers for linear programming
DOI10.1023/A:1015460004163zbMATH Open1041.90028OpenAlexW1549624355WikidataQ57733265 ScholiaQ57733265MaRDI QIDQ700762FDOQ700762
Authors: Dennis Cheung, Felipe Cucker 
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
Recommendations
- On the expected condition number of linear programming problems
- Solving linear programs with finite precision. I: Condition numbers and random programs
- Smoothed analysis of condition numbers and complexity implications for linear programming
- Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
- A new condition number for linear programming
Linear programming (90C05) Sensitivity, stability, parametric optimization (90C31) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Some perturbation theory for linear programming
- Title not available (Why is that?)
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- Some characterizations and properties of the ``distance to the ill-posedness and the condition measure of a conic linear system
- 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
- A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine
- Condition numbers for polyhedra with real number data
- Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm
- A new condition number for linear programming
- Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
- Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
Cited In (17)
- Title not available (Why is that?)
- Smoothed analysis of condition numbers and complexity implications for linear programming
- Probabilistic analysis of the Grassmann condition number
- Title not available (Why is that?)
- Robust smoothed analysis of a condition number for linear programming
- The expected number of extreme points of a random linear program
- Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
- Metric regularity of semi-infinite constraint systems
- Coverage processes on spheres and condition numbers for linear programming
- High probability analysis of the condition number of sparse polynomial systems
- Smoothed analysis of complex conic condition numbers
- Computational complexity of kernel-based density-ratio estimation: a condition number analysis
- Perturbation analysis of linear programming problems with random parameters
- A new condition number for linear programming
- Solving linear programs with finite precision. I: Condition numbers and random programs
- On the expected condition number of linear programming problems
- On the average condition of random linear programs
This page was built for publication: Probabilistic analysis of condition numbers for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q700762)
