Smoothed analysis of condition numbers and complexity implications for linear programming
From MaRDI portal
Publication:623362
DOI10.1007/s10107-009-0278-5zbMath1218.90109MaRDI QIDQ623362
Daniel A. Spielman, Shang-Hua Teng, John Dunagan
Publication date: 14 February 2011
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-009-0278-5
Related Items
Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Robust smoothed analysis of a condition number for linear programming, Coverage processes on spheres and condition numbers for linear programming, Smooth analysis of the condition number and the least singular value, Smoothed Analysis of Local Search Algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Probabilistic analysis of condition numbers for linear programming
- A new polynomial-time algorithm for linear programming
- An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
- The reverse isoperimetric problem for Gaussian measure
- Some perturbation theory for linear programming
- On the expected condition number of linear programming problems
- Smoothed analysis of termination of linear programming algorithms
- 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
- Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure.
- A lower bound on the number of iterations of long-step primal-dual linear programming algorithms
- Linear programming, complexity theory and elementary functional analysis
- How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds
- Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming
- A Primal-Dual Algorithm for Solving Polyhedral Conic Systems with a Finite-Precision Machine
- Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
- Smoothed analysis of algorithms
- Probabilistic Models for Linear Programming
- An $O(\sqrt{n} L)$-Iteration Large-Step Primal-Dual Affine Algorithm for Linear Programming
- On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
- Feature Article—Interior Point Methods for Linear Programming: Computational State of the Art
- Linear Programming in O([n3/ln nL) Operations]
- Condition-Based Complexity of Convex Optimization in Conic Linear Form via the Ellipsoid Algorithm
- Incorporating Condition Measures into the Complexity Theory of Linear Programming
- Ill-Posedness and the Complexity of Deciding Existence of Solutions to Linear Programs
- Understanding the Geometry of Infeasible Perturbations of a Conic Linear System
- Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems
- Algorithms and Data Structures
- A simple polynomial-time rescaling algorithm for solving linear programs
- A new condition number for linear programming
