scientific article; zbMATH DE number 2119754

zbMath1058.65062MaRDI QIDQ4829029

John Dunagan, Avrim L. Blum

Publication date: 29 November 2004

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

zbMATH Keywords

linear programminggreedy algorithmsimplex algorithmperceptron algorithmsmoothed complexity

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05) Complexity and performance of numerical algorithms (65Y20)

Related Items

Smoothed analysis of binary search trees, Smoothed Analysis of Local Search Algorithms, Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design, Smoothed Analysis on Connected Graphs, Smoothed analysis of condition numbers and complexity implications for linear programming, Computational complexity of kernel-based density-ratio estimation: a condition number analysis, Some remarks on the condition number of a real random square matrix, Settling the Complexity of Local Max-Cut (Almost) Completely, A simple polynomial-time rescaling algorithm for solving linear programs, Unnamed Item, Smoothed analysis of probabilistic roadmaps, Conditioning of random conic systems under a general family of input distributions