Robust smoothed analysis of a condition number for linear programming

DOI10.1007/s10107-010-0346-xzbMath1242.90098arXiv0803.0925MaRDI QIDQ662310

Peter Bürgisser, Dennis Amelunxen

Publication date: 22 February 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0803.0925

zbMATH Keywords

linear programming; perturbations; condition numbers; smoothed analysis

Mathematics Subject Classification ID

60D05: Geometric probability and stochastic geometry

90C31: Sensitivity, stability, parametric optimization

90C05: Linear programming

52A22: Random convex sets and integral geometry (aspects of convex geometry)

Related Items

Probabilistic analyses of condition numbers, Sharp recovery bounds for convex demixing, with applications, On a problem posed by Steve Smale, Coverage processes on spheres and condition numbers for linear programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smoothed analysis of condition numbers and complexity implications for linear programming
• Probabilistic analysis of condition numbers for linear programming
• Smooth approximation of convex bodies
• Smoothed analysis of complex conic condition numbers
• Coverage processes on spheres and condition numbers for linear programming
• Adversarial smoothed analysis
• Conditioning of random conic systems under a general family of input distributions
• 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
• Linear programming, complexity theory and elementary functional analysis
• 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
• The probability that a slightly perturbed numerical analysis problem is difficult
• Smoothed analysis of algorithms
• The Probability That a Numerical Analysis Problem is Difficult
• A Problem in Geometric Probability.
• The Relaxation Method for Solving Systems of Linear Inequalities
• The kinematic formula in Riemannian homogeneous spaces
• Incorporating Condition Measures into the Complexity Theory of Linear Programming
• Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems
• Steiner’s formulae on a general 𝑆ⁿ⁺¹
• A new condition number for linear programming