Smoothed analysis of condition numbers and complexity implications for linear programming
From MaRDI portal
The paper performs a smoothed analysis of Renegar's condition number for linear programming by analysing the distribution of the distance to ill-posedness of a linear program subject to a slight Gaussian perturbation. This analysis demonstrates that if there is a little bit of imprecision or noise in the input data, then the linear program is unlikely to be poorly conditioned, and hence can be solved quickly by interior-point algorithms.
Recommendations
- Robust smoothed analysis of a condition number for linear programming
- Smoothed analysis of termination of linear programming algorithms
- Solving linear programs with finite precision. I: Condition numbers and random programs
- Smoothed analysis of condition numbers
- Probabilistic analysis of condition numbers for linear programming
Cites work
- A lower bound on the number of iterations of long-step primal-dual linear programming algorithms
- A new condition number for linear programming
- A new polynomial-time algorithm for linear programming
- A primal-dual algorithm for solving polyhedral conic systems with a finite-precision machine
- A simple polynomial-time rescaling algorithm for solving linear programs
- An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming
- An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
- Average performance of a self-dual interior point algorithm for linear programming
- Complexity of convex optimization using geometry-based measures and a reference point
- Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system
- Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm
- Feature Article—Interior Point Methods for Linear Programming: Computational State of the Art
- How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 4199963 (Why is no real title available?)
- scientific article; zbMATH DE number 3517666 (Why is no real title available?)
- scientific article; zbMATH DE number 554743 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 2119754 (Why is no real title available?)
- scientific article; zbMATH DE number 3214278 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- scientific article; zbMATH DE number 3273551 (Why is no real title available?)
- scientific article; zbMATH DE number 964349 (Why is no real title available?)
- Ill-Posedness and the Complexity of Deciding Existence of Solutions to Linear Programs
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure.
- Linear Programming in O([n3/ln n]L) Operations
- Linear programming, complexity theory and elementary functional analysis
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- On the expected condition number of linear programming problems
- Probabilistic analysis of an infeasible-interior-point algorithm for linear programming
- Probabilistic analysis of condition numbers for linear programming
- Probabilistic Models for Linear Programming
- Smoothed analysis of algorithms
- Smoothed analysis of termination of linear programming algorithms
- Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
- Smoothed analysis. Motivation and discrete models
- Some perturbation theory for linear programming
- Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems
- The reverse isoperimetric problem for Gaussian measure
- Understanding the Geometry of Infeasible Perturbations of a Conic Linear System
Cited in
(13)- Smoothed analysis of termination of linear programming algorithms
- Solving linear programs with finite precision. I: Condition numbers and random programs
- Smooth analysis of the condition number and the least singular value
- Smoothed analysis of local search algorithms
- Smoothed analysis of algorithms
- Smoothed Analysis of Integer Programming
- Recent progress on the combinatorial diameter of polytopes and simplicial complexes
- scientific article; zbMATH DE number 2113994 (Why is no real title available?)
- Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
- Robust smoothed analysis of a condition number for linear programming
- Probabilistic analysis of condition numbers for linear programming
- Smoothed analysis of integer programming
- Coverage processes on spheres and condition numbers for linear programming
This page was built for publication: Smoothed analysis of condition numbers and complexity implications for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q623362)
