Conditioning of random conic systems under a general family of input distributions

DOI10.1007/S10208-008-9034-0zbMath1193.90199OpenAlexW1991524217MaRDI QIDQ1029212

Raphael Hauser, Tobias Müller

Publication date: 10 July 2009

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10208-008-9034-0

Mathematics Subject Classification ID

Multivariate distribution of statistics (62H10) Abstract computational complexity for mathematical programming problems (90C60) Sensitivity, stability, parametric optimization (90C31) Linear programming (90C05) Random matrices (algebraic aspects) (15B52)

Related Items (4)

The average condition number of most tensor rank decomposition problems is infinite ⋮ Robust smoothed analysis of a condition number for linear programming ⋮ Coverage processes on spheres and condition numbers for linear programming ⋮ Adversarial smoothed analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the expected condition number of linear programming problems
• Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure.
• Linear programming, complexity theory and elementary functional analysis
• Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming
• A Primal-Dual Algorithm for Solving Polyhedral Conic Systems with a Finite-Precision Machine
• On the average number of steps of the simplex method of linear programming
• Smoothed analysis of algorithms
• The Relaxation Method for Solving Systems of Linear Inequalities
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems
• A simple polynomial-time rescaling algorithm for solving linear programs
• Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
• A new condition number for linear programming

This page was built for publication: Conditioning of random conic systems under a general family of input distributions