CORMSIS Seminar - The Support of Integer Optimal Solutions, Dr Timm Oertel (Cardiff) Seminar
- Time:
- 14:00 - 15:00
- Date:
- 25 October 2018
- Venue:
- Room 8031, Building 54, Mathematical Sciences, University of Southampton, Highfield Campus, SO17 1BJ
For more information regarding this seminar, please email Professor Joerg Fliege at J.Fliege@southampton.ac.uk .
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
Dr Timm Oertel , Cardiff University. Timm's research interests include Theoretical and algorithmic aspects of integer and mixed-integer convex optimization; and Convex and discrete geometry.