Spring 2020

Distance-Sparsity Transference for Lattice Points in Knapsack Polytopes

Thursday, Feb. 20, 2020 11:30 am12:00 pm PST

Add to Calendar


Iskander Aliev, Cardiff University


Calvin Lab Auditorium

Let P be a knapsack polytope that contains integer points. We prove that for any vertex v of P there exists an integer point z in P that satisfies a transference inequality linking the maximum norm distance ||v-z|| and the size of support of z. Further, for general integer linear programs we obtain a resembling result that connects the minimum absolute nonzero entry of a solution with the size of its support.