Colloquium by Marcel Celaya (ETH, Zürich): Improving the Cook et al. Proximity Bound Given Integral Valued Constraints
Given an optimal solution to a linear program, how far away can a nearest optimal integral solution be? In 1986 Cook, Gerards, Schrijver, and Tardos gave a bound for this distance, known as proximity, which depends only on the dimension and the largest possible magnitude of any subdeterminant of the corresponding constraint matrix. In this talk I will briefly survey this problem, describe some long standing related conjectures, and highlight some recent developments including a recent improvement to the Cook et al. bound when the dimension is at least 2. This is joint work with Joseph Paat, Stefan Kuhlmann, and Robert Weismantel.
Time & Location
May 09, 2022 | 04:00 PM s.t.
Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)