N&O Lecture Stefan Weltge (ETH): Polytopes in the 0/1-Cube with Bounded Chvátal-Gomory Rank

Everyone who is interested is welcome to attend this CWI public lecture of Stefan. Abstract: Let P be any polytope contained in [0,1]^n and S be the set ofits integer points.
  • What Networks & Optimization
  • When 22-02-2017 from 10:00 to 11:00 (Europe/Amsterdam / UTC100)
  • Where Room L017, CWI, Science Park 123, Amsterdam
  • Web Visit external website
  • Add event to calendar iCal

Everyone who is interested is welcome to attend this CWI public lecture of Stefan.

Abstract: Let P be any polytope contained in [0,1]^n and S be the set of
its integer points. We prove that P has bounded Chvátal-Gomory rank
(CG-rank) provided that S has bounded pitch and bounded gap, where the
pitch is the minimum integer p such that all p-dimensional faces of [0,1]^n
have a nonempty intersection with S, and the gap is a measure of the size
of the facet coefficients of conv(S). Let H[S] denote the subgraph of the
n-cube induced by the vertices not in S. We prove that if H[S] does not
contain a subdivision of a large complete graph, then both the pitch and
the gap are bounded.  By our main result, this implies that the CG-rank of
R is bounded as a function of the treewidth of H[S]. This generalizes a
recent theorem of Cornuéjols and Lee (2016), who proved that the CG-rank is
always bounded if the treewidth of H[S] is at most 2. This is joint work
with Yohann Benchetrit, Samuel Fiorini and Tony Huynh.