Smoothed analysis of termination of linear programming algorithms

DOI10.1007/S10107-003-0448-9MaRDI QIDQ1403294zbMATH OpenOpenAlexFDO

Authors Daniel A. Spielman, Shang-Hua Teng

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

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

Recommendations

• Smoothed analysis of condition numbers and complexity implications for linear programming
• scientific article; zbMATH DE number 2119754
• Smoothed analysis of algorithms
• A friendly smoothed analysis of the simplex method
• A friendly smoothed analysis of the simplex method

Cited in

(17)

• Smoothed analysis of condition numbers and complexity implications for linear programming
• State estimation on positive Markovian jump systems with time-varying delay and uncertain transition probabilities
• Robust smoothed analysis of a condition number for linear programming
• 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
• Smoothed analysis of binary search trees
• Positive consensus for multi-agent systems with average dwell time switching
• Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis
• Smoothed analysis of complex conic condition numbers
• The probability that a slightly perturbed numerical analysis problem is difficult
• scientific article; zbMATH DE number 2119754 (Why is no real title available?)
• Smoothed Analysis of Integer Programming
• Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
• Smoothed analysis of probabilistic roadmaps
• Approximation schemes for packing with item fragmentation
• The average condition number of most tensor rank decomposition problems is infinite
• Smoothed analysis of local search algorithms

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1403294)