An arbitrary starting homotopy-like simplicial algorithm for computing an integer point in a class of polytopes

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

5 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)609-633
Journal / PublicationSIAM Journal on Discrete Mathematics
Volume23
Issue number2
Publication statusPublished - 2009

Abstract

An arbitrary starting homotopy-like simplicial algorithm is developed for computing an integer point in a polytope given by P = {x | Ax ≤ b} satisfying that each row of A has at most one positive entry. The algorithm is derived from an introduc tion of an integer labeling rule and an application of a triangulation of the space Rn × [0, 1]. It consists of two phases, one of which forms an (n + 1)-dimensional pivoting procedure and the other an n-dimensional pivoting procedure. Starting from an arbitrary integer point in Rn ×{0}, the algorithm interchanges from one phase to the other, if necessary, AND follows a finite simplicial path that either leads to an integer point in the polytope or proves that no such point exists. © 2009 Society for Industrial and Applied Mathematics.

Research Area(s)

  • Homotopy-like simplicial algorithm, Integer labeling, Integer point, Integer programming, Pivoting procedure, Polytope, Triangulation