Symbolic Computation Group
David R. Cheriton School of Computer Science
|
|
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.