A simplicial algorithm for testing the integral properties of polytopes: A revision

Z.F. Yang

Research output: Working paperDiscussion paperOther research output

208 Downloads (Pure)

Abstract

Given an arbitrary polytope P in the n-dimensional Euclidean space R n , the question is to determine whether P contains an integral point or not. We propose a simplicial algorithm to answer this question based on a specifc integer labeling rule and a specific triangulation of R n . Starting from an arbitrary integral point ofR n , the algorithm terminates within a finite number of steps with either an integral point in P or proving there is no integral point inP. One prominent feature of the algorithm is that the structure of the algorithm is very simple and itcanbeeasily implemented on a computer. Moreover, the algorithm is computationally very simple, exible and stable.
Original languageEnglish
PublisherCentER, Center for Economic Research
Volume1994-89
Publication statusPublished - 1994

Publication series

NameCentER Discussion Paper
Volume1994-89

Keywords

  • Linear Programming
  • operations research

Fingerprint

Dive into the research topics of 'A simplicial algorithm for testing the integral properties of polytopes: A revision'. Together they form a unique fingerprint.

Cite this