Заседание научного семинара лаборатории ЛАТАС
Тема: About vertices, facets and diameter of delta-modular polyhedra.
Докладчик: Dmitry Gribanov (MIPT and lab LATNA HSE)
Дата и время проведения: 19 марта 16:00
Место проведения: Нижний Новгород, ул. Родионова, д.136, ауд. 401
Abstract: A polyhedron P defined by the system Ax≤b is called Δ-modular if all rank-order subdeterminants of the integer matrix A are bounded in absolute value by Δ. It turns out that the number of vertices, the number of facets, and the graph diameter of P are all bounded by linear functions in terms of Δ.
The main focus of this talk is an asymptotically tight upper bound on the number of vertices, which follows directly from the symmetric version of Macbeath's theorem. Additionally, we aim to establish an upper bound on the graph diameter of P, which depends polynomially on both the dimension and Δ.
Приглашаются все желающие!
Явка аспирантов школы компьютерных наук обязательна.