Smoothed analysis of condition numbers and complexity implications for linear programming
From MaRDI portal
Publication:623362
DOI10.1007/s10107-009-0278-5zbMath1218.90109OpenAlexW2136487406MaRDI 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 (5)
Smooth analysis of the condition number and the least singular value ⋮ Smoothed Analysis of Local Search Algorithms ⋮ 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
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
This page was built for publication: Smoothed analysis of condition numbers and complexity implications for linear programming
