Skip to main navigation Skip to Content
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 
COPYRIGHT 2012 © ALL RIGHTS RESERVED
Please submit your comments or questions here, or contact Webmaster  ipmic@ipm.ir