Robust smoothed analysis of a condition number for linear programming

DOI10.1007/S10107-010-0346-XzbMath1242.90098arXiv0803.0925OpenAlexW2172032236MaRDI 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 programmingperturbationscondition numberssmoothed analysis

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Sensitivity, stability, parametric optimization (90C31) Linear programming (90C05) Random convex sets and integral geometry (aspects of convex geometry) (52A22)

Related Items (4)

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 ⋮ Probabilistic analyses of condition numbers

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

This page was built for publication: Robust smoothed analysis of a condition number for linear programming