Name
Title | ||
|---|---|---|
Probabilistic Analysis of an Infeasible-Interior-Point Algorithm for Linear Programming |
Abstract | ||
|---|---|---|
We consider an infeasible-interior-point algorithm, endowed with a finite termination scheme, applied to random linear programs generated according to a model of Todd. Such problems have degenerate optimal solutions, and possess no feasible starting point. We use no information regarding an optimal solution in the initialization of the algorithm. Our main result is that the expected number of iterations before termination with an exact optimal solution is On lnn. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1287/moor.24.1.176 | Math. Oper. Res. |
Keywords | DocType | Volume |
finite termination scheme,optimal solution,expected number,probabilistic analysis,infeasible-interior-point algorithm,linear programming,random linear program,exact optimal solution,main result,average-case behavior,n ln | Journal | 24 |
Issue | ISSN | Citations |
1 | 0364-765X | 10 |
PageRank | References | Authors |
0.84 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kurt M. Anstreicher | 1 | 633 | 86.40 |
| Jun Ji | 2 | 41 | 6.82 |
| Florian A. Potra | 3 | 305 | 34.71 |
| Yinyu Ye | 4 | 5201 | 497.09 |