Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure.

DOI10.1006/jcom.2002.0640zbMath1046.90040OpenAlexW2084215264MaRDI QIDQ1872636

Petra Huhn, Karl Heinz Borgwardt

Publication date: 14 May 2003

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://opus.bibliothek.uni-augsburg.de/opus4/files/29470/%2831%29Interior%20Point%20methods%20Worst%20-Case%20and%20Average%20Case%20Analysis.pdf

zbMATH Keywords

linear programminginterior-point methodsprobabilistic analysis.

Mathematics Subject Classification ID

Linear programming (90C05)

Related Items

Smoothed analysis of condition numbers and complexity implications for linear programming, On the probabilistic complexity of finding an approximate solution for linear programming, Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions, Conditioning of random conic systems under a general family of input distributions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Probabilistic analysis of optimization algorithms - some aspects from a practical point of view
• Finding an interior point in the optimal face of linear programs
• Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming
• Erratum: A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes
• On the average number of steps of the simplex method of linear programming
• New results on the average behavior of simplex algorithms
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• Probabilistic Models for Linear Programming
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems