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 (15)

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

This page was built for publication: Smoothed analysis of termination of linear programming algorithms