scientific article; zbMATH DE number 1962932

zbMath1056.65148arXivmath/0212413MaRDI QIDQ4418806

Shang-Hua Teng, Daniel A. Spielman

Publication date: 2002

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

condition numberinterior point methodsimplex methodnumerical algorithmsperceptron methodsmoothed (complexity) analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05) Interior-point methods (90C51) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity and performance of numerical algorithms (65Y20)

Related Items (30)

Smooth analysis of the condition number and the least singular value ⋮ Smoothed analysis of \(\kappa(A)\) ⋮ The smallest singular value of random rectangular matrices with no moment assumptions on entries ⋮ Universality of the least singular value for sparse random matrices ⋮ Random matrices: overcrowding estimates for the spectrum ⋮ Smoothed analysis of complex conic condition numbers ⋮ From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices ⋮ On the complexity of the Plantinga-Vegter algorithm ⋮ Condition numbers for the cube. I: Univariate polynomials and hypersurfaces ⋮ Quantitative invertibility of non-Hermitian random matrices ⋮ Randomized preprocessing versus pivoting ⋮ The least singular value of a random symmetric matrix ⋮ Around the circular law ⋮ On a problem posed by Steve Smale ⋮ Robust smoothed analysis of a condition number for linear programming ⋮ The smallest singular value of a shifted $d$-regular random square matrix ⋮ Random matrices: tail bounds for gaps between eigenvalues ⋮ The probability that a slightly perturbed numerical analysis problem is difficult ⋮ Stochastic perturbations and smooth condition numbers ⋮ The Littlewood-Offord problem and invertibility of random matrices ⋮ Randomized preprocessing of homogeneous linear systems of equations ⋮ Adversarial smoothed analysis ⋮ General formulas for the smoothed analysis of condition numbers ⋮ Random matrices: The distribution of the smallest singular values ⋮ Smoothed analysis of symmetric random matrices with continuous distributions ⋮ On a condition number of general random polynomial systems ⋮ Spectral statistics of non-selfadjoint operators subject to small random perturbations ⋮ A randomized Kaczmarz algorithm with exponential convergence ⋮ Smoothed analysis of probabilistic roadmaps ⋮ Smoothed analysis for the condition number of structured real polynomial systems

This page was built for publication: