Average case complexity results for a centering algorithm for linear programming problems under Gaussian distributions |
| |
Authors: | Petra Huhn Verena Wehlitz |
| |
Affiliation: | Institute for Mathematics, Clausthal University of Technology, Erzstr. 1, 38678 Clausthal-Zellerfeld, Germany |
| |
Abstract: | To solve linear programming problems by interior point methods an approximately centered interior point has to be known. Such a point can be found by an algorithmic approach – a so-called phase 1 algorithm or centering algorithm. For random linear programming problems distributed according to the rotation symmetry model, especially with normal distribution, we present probabilistic results on the quality of the origin as starting point and the average number of steps of a centering algorithm. |
| |
Keywords: | Linear programming Interior point methods Average case complexity of algorithms |
本文献已被 ScienceDirect 等数据库收录! |