Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions

DOI10.1016/J.EJOR.2007.12.030MaRDI QIDQ1002052zbMATH OpenOpenAlexFDO

Authors Petra Huhn, Verena Wehlitz

Publication date 23 February 2009

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2007.12.030

zbMATH Keywords

average case complexity of algorithmsinterior point methodslinear programming

Mathematics Subject Classification ID

Linear programming (90C05) Interior-point methods (90C51)

Recommendations

• Toward Probabilistic Analysis of Interior-Point Algorithms for Linear Programming
• scientific article; zbMATH DE number 1487877
• scientific article; zbMATH DE number 4197740
• Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure.
• Average number of iterations of some polynomial interior-point -- algorithms for linear programming

Cites work

• A combined phase I-phase II projective algorithm for linear programming
• A combined phase I-phase II scaled potential algorithm for linear programming
• An Infeasible-Interior-Point Predictor-Corrector Algorithm for Linear Programming
• An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
• Combining phase I and phase II in a potential reduction algorithm for linear programming
• scientific article; zbMATH DE number 590363 (Why is no real title available?)
• scientific article; zbMATH DE number 1041033 (Why is no real title available?)
• scientific article; zbMATH DE number 1131479 (Why is no real title available?)
• scientific article; zbMATH DE number 1487877 (Why is no real title available?)
• scientific article; zbMATH DE number 1495246 (Why is no real title available?)
• scientific article; zbMATH DE number 1528193 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 3277086 (Why is no real title available?)
• Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure.
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• Probabilistic analysis of optimization algorithms - some aspects from a practical point of view
• Probabilistic Models for Linear Programming
• Superlinear convergence of infeasible-interior-point methods for linear programming

Cited in

(3)

• On the probabilistic complexity of finding an approximate solution for linear programming
• A randomized center path method for a class of linear programming problems
• scientific article; zbMATH DE number 1487877 (Why is no real title available?)

This page was built for publication: Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions

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