Smoothed analysis of termination of linear programming algorithms

DOI10.1007/s10107-003-0448-9zbMath1035.90042OpenAlexW63574446MaRDI QIDQ1403294

Shang-Hua Teng, Daniel A. Spielman

Publication date: 1 September 2003

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

Full work available at URL: https://doi.org/10.1007/s10107-003-0448-9

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Linear programming (90C05) Interior-point methods (90C51)

Related Items

Smoothed analysis of binary search trees, Smoothed Analysis of Local Search Algorithms, Smoothed analysis of complex conic condition numbers, Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design, Smoothed analysis of condition numbers and complexity implications for linear programming, The average condition number of most tensor rank decomposition problems is infinite, A Friendly Smoothed Analysis of the Simplex Method, \(l_1\)-gain performance analysis and positive filter design for positive discrete-time Markov jump linear systems: a linear programming approach, Approximation schemes for packing with item fragmentation, Robust smoothed analysis of a condition number for linear programming, Positive consensus for multi-agent systems with average dwell time switching, The probability that a slightly perturbed numerical analysis problem is difficult, State estimation on positive Markovian jump systems with time-varying delay and uncertain transition probabilities, Unnamed Item, Smoothed analysis of probabilistic roadmaps