An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex |
| |
| Authors: | G. de Ghellinck J. -Ph. Vial |
| |
| Affiliation: | (1) CORE, Louvain la Neuve, Belgium;(2) Faculté SES, Université de Genève, Switzerland |
| |
| Abstract: | We present an extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex. It is shown that in at most O(nL) steps, the algorithm produces a feasible point or proves that the problem has no solution. The complexity is O(n 2 m 2 L) arithmetic operations. The algorithm is endowed with two new powerful stopping criteria. |
| |
| Keywords: | Feasibility problem linear programming polynomial algorithm projective geometry |
| 本文献已被 SpringerLink 等数据库收录！ |
