Symbolic Computation Group

David R. Cheriton School of Computer Science
University of Waterloo, Waterloo, Ontario, Canada

Friday, June 9, 2017, at Western University
Computing the Integer Points of a Polyhedron
Rui-Juan Jing, KLMM, UCAS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences

Abstract:

Let K be a polyhedron in R^d, given by a system of m linear inequalities, with rational number coefficients bounded over in absolute value by L. We propose an algorithm for computing an irredundant representation of the integer points of K, in terms of “simpler” polyhedra, each of them having at least one integer point. Using the terminology of W. Pugh: for any such polyhedron P, no integer point of its grey shadow extends to an integer point of P. We show that, under mild assumptions, our algorithm runs in exponential time w.r.t. d and in polynomial w.r.t m and L. We report on a software experimentation.

 

Last modified on Monday, 12 August 2024, at 23:34 hours.