4 Presentations

• 
  10:30 AM - 10:55 AM

  The Width of 4-Prismatoids

  • Tamon Stephen, presenter, Simon Fraser University

  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

  • Andrew Baker, presenter, McMaster University
  • Antoine Deza, McMaster University
  • Frantisek Franek, McMaster University

  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

  • Dilson Lucas Pereira, presenter, Universidade Federal de Minas Gerais
  • Michel Gendreau, Polytechnique Montréal
  • Alexandre Cunha, Universidade Federal de Minas Gerais

  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

  • Patricia Gillett, presenter, Polytechnique Montréal
  • Miguel F. Anjos, GERAD, Polytechnique Montréal

  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.