“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 118 |
|
| Abstract: | |
|
Over the rationals, the general linear programming problem is equivalent to the convex hull problem of determining if a given
m×n matrix H has a nontrivial nonnegative zero. We give a polynomial time algorithm that either finds a nontrivial
nonnegative zero of H, or it obtains a hyperplane separating the column vectors of H from the origin. In particular, the
algorithm provides an alternate proof of a strengthened version of Gordan's duality theorem, previously proved by the author.
The algorithm which is motivated by this duality theorem is analogous to Karmarkar's algorithm but its analysis is much simpler.
Download TeX format |
|
| back to top | |
