On the size of integer programs

  • Matthias Schymura (University of Rostock)
G3 10 (Lecture hall)


We are interested in a combinatorial question related to the ongoing interest in understanding the complexity of integer linear programming with bounded subdeterminants.

Given a positive integer Delta and a full-rank integer matrix A with m rows such that the absolute value of every m-by-m minor of A is bounded by Delta, at most how many pairwise distinct columns can A have? The case Delta = 1 is the classical result of Heller (1957) saying that the maximal number of pairwise distinct columns of a totally unimodular integer matrix with m rows is m^2 + m + 1. If m >= 3 and Delta >= 3, the precise answer to this combinatorial question is not known, but bounds of order O(Delta^2 m^2) have been proven by Lee et al. (2021). In the talk, I will discuss our approach to the problem which rests on counting columns of A by residue classes of a suitably defined integer lattice. As a result, we obtain the first bound that is linear in Delta and polynomial (of low degree) in the dimension m.

This is joint work with Gennadiy Averkov.

Katharina Matschke

MPI for Mathematics in the Sciences Contact via Mail