Springe direkt zu Inhalt

Colloquium by Marcel Celaya (ETH, Zürich): Improving the Cook et al. Proximity Bound Given Integral Valued Constraints

Jul 04, 2022 | 04:00 PM s.t.

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

Jul 04, 2022 | 04:00 PM s.t.

Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
10623 Berlin
Room MA 041 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)