2012/10/23 by Gennadiy Averkov, Michele Conforti, Averkov, Gennadiy +7
Computer Science · Engineering · Mathematics · #52B20 #52C07 #90C10 #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Commutative Algebra and Its Applications #FOS: Mathematics #Metric Geometry (math.MG) #Optimization and Control (math.OC) #Polynomial and algebraic computation #math.CO #math.MG #math.OC #msc:52B20 #msc:52C07 #msc:90C10
paper · pdf · doi:10.48550/arxiv.1210.6280
13 pages, 2 figures - the introduction has been extended and an extra chapter has been added
openalex publication_date 2012/10/23 · arxiv created 2012/11/08 · arxiv updated 2012/11/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given an integral polyhedron P and a rational polyhedron Q living in the same n-dimensional space and containing the same integer points as P, we investigate how many iterations of the Chvátal-Gomory closure operator have to be performed on Q to obtain a polyhedron contained in the affine hull of P. We show that if P contains an integer point in its relative interior, then such a number of iterations can be bounded by a function depending only on n. On the other hand, we prove that if P is not full-dimensional and does not contain any integer point in its relative interior, then no finite bound on the number of iterations exists.