Skip to main navigationSkip to main content
The University of Southampton
CORMSIS Centre for Operational Research, Management Sciences and Information Systems

The Support of Integer Optimal Solutions -- Talk by Timm Oertel Event

25 October 2018

For more information regarding this event, please email Joerg Fliege at .

Event details

The support of a vector is the number of nonzero-components. We show that given an integral m x n matrix A, the integer linear optimization problem max{ c^Tx : Ax = b, x>=0, x in Z^n} has an optimal solution whose support is bounded by 2m log(2 sqrt(m) ||A||), where ||A|| is the largest absolute value of an entry of A. Compared to previous bounds, the one presented here is independent on the objective function. We furthermore provide a nearly matching asymptotic lower bound on the support of optimal solutions.

Speaker information

Timm Oertel ,Cardiff University ,is a Lecturer of Mathematics. He received his PhD from ETH in 2014.

Privacy Settings