N&O Lecture Stefan Weltge (ETH): Polytopes in the 0/1-Cube with Bounded Chvátal-Gomory Rank
- https://www.cwi.nl/events/2017/n-o-lectures-2017/no-lecture-stefan-weltge-eth-polytopes-in-01-cube-bounded-chvatal-gomory-rank
- N&O Lecture Stefan Weltge (ETH): Polytopes in the 0/1-Cube with Bounded Chvátal-Gomory Rank
- 2017-02-22T10:00:00+01:00
- 2017-02-22T11:00:00+01:00
- 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 Feb 22, 2017 from 10:00 AM to 11:00 AM (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.