Simplices by Point-Sliding and the Yamnitsky-Levin Algorithm

U. Faigle, M.M.G. Hunting, Walter Kern, R. Prakash, K.J. Supowit

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

Yamnitsky and Levin proposed a variant of Khachiyan's ellopsoid method for testing feasibility of systems of linear inequalities that also runs in polynomial time but uses simplices instead of ellipsoids. Starting with then-simplexS and the half-space {x¦aTx ≤ β}, the algorithm finds a simplexSYL of small volume that enclosesS ∩ {x¦aTx ≤ β}. We interpretSYL as a simplex obtainable by point-sliding and show that the smallest such simplex can be determined by minimizing a simple strictly convex function. We furthermore discuss some numerical results. The results suggest that the number of iterations used by our method may be considerably less than that of the standard ellipsoid method.
Original languageUndefined
Pages (from-to)131-142
Number of pages12
JournalMathematical methods of operations research
Volume46
Issue number46
DOIs
Publication statusPublished - 1997

Keywords

  • Ellipsoid method - linear programming - simplex - volume
  • METIS-140783
  • IR-71486

Cite this