10:30 AM - 10:55 AM
The Width of 4-Prismatoids
Santos' recent construction of a counterexample to the Hirsch conjecture highlights a
particular 5-dimensional "prismatoid" polytope. We use the Euler characteristic to prove
that there is no analogous 4-dimensional prismatoid.
10:55 AM - 11:20 AM
A Computational Framework for Determining Run-Maximal Strings
We investigate the maximum runs in strings with fixed length and distinct characters. Exploiting
the notion of an r-cover, we obtain all previously known values on binary strings and extend the
computation to length 74. Noticeably, we exhibit a run-maximal string containing aaaa.
11:20 AM - 11:45 AM
Lower Bounds and Exact Algorithms for the Quadratic Minimum Spanning Tree Problem
In this work we address the Quadratic Minimum Spanning Tree Problem. Initially we develop a branch-and-bound algorithm using an RLT lower bound for the problem. Then, we propose a hierarchy of lower bounds of increasing strength. We present results concerning the strength and computational complexity of computing these bounds. A branch-and-bound algorithm is developed for one of the cases.
11:45 AM - 12:10 PM
Semidefinite Programming Approaches for a Class of Complementarity Problems
We consider a class of complementarity problems with non-convex quadratic objective functions. We discuss the difficulty of globally solving problems of this class and the potential for semidefinite programming relaxations to give tighter bounds. We present one such semidefinite programming relaxation in depth and discuss ongoing efforts to further strengthen the model.