Return to Colloquia & Seminar listing
Polynomial upper bounds on the number of differing columns of $\Delta$-modular integer programs
Mathematics of Data & Decisions| Speaker: | Luze Xu, UC Davis |
| Related Webpage: | https://sites.google.com/umich.edu/xuluze/home |
| Location: | Zoom |
| Start time: | Thu, Oct 27 2022, 9:00AM |
We study integer-valued matrices with bounded determinants. Such matrices appear in the theory of integer programs (IP) with bounded determinants. One of the first works about the structure of the matrix with bounded determinants was that of Heller, who identified the maximum number of differing columns in a totally unimodular matrix. Each extension of Heller's bound to general determinants has been super-polynomial in the determinants or the number of equations. We provide the first column bound that is polynomial in both values. Furthermore, we show a tight bound on the number of differing columns in a bimodular matrix; this is the first tight bound since Heller. Our analysis reveals combinatorial properties of bimodular IPs that may be of independent interest.
https://ucdavis.zoom.us/j/97068195483?pwd=dDZNYmtVcVZ3WUkzc0F6eFN0YXRXdz09