“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 118
School of Mathematics
  Title:   A simple polynomial time algorithm for a convex hull problem equivalent to linear programming
  Author(s):  B. Kalantari
  Status:   In Proceedings
  Proceeding: Combinatorics Advances
  Vol.:  329
  Year:  1996
  Pages:   207-216
  Editor:  Math. Appl.(C.J. Colbourn and E.S. Mahmoodian, eds.)
  Publisher(s):   Kluwer Academic Press, Dordrecht
  Supported by:  IPM
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
scroll left or right