Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems
From MaRDI portal
Publication:5930724
DOI10.1007/s101070100200zbMath0978.90069MaRDI QIDQ5930724
Yinyu Ye, Michael J. Todd, Tunçel, Levent
Publication date: 12 February 2002
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Interior-point methods (90C51)
Related Items
Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure., Smoothed analysis of complex conic condition numbers, Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, Computational complexity of kernel-based density-ratio estimation: a condition number analysis, A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms, On the probabilistic complexity of finding an approximate solution for linear programming, Probabilistic analysis of condition numbers for linear programming, Improved complexity results on solving real-number linear feasibility problems, Conditioning of random conic systems under a general family of input distributions, A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
