Calendrier

Seminar: How to improve an upper bound on the stability number

Seminar:  How to improve an upper bound on the stability number

Joint seminar with the Canada Research Chair in Discrete Nonlinear Optimization in Engineering  and the GERAD


Title: How to improve an upper bound on the stability number


Speaker: Elisabeth Gaar – Alpen-Adria-Universität Klagenfurt, Austria


Abstract:



The stable set problem is a well-known combinatorial optimization problem. It is NP-complete and furthermore hard to approximate, hence one wants to get tight upper bounds for the stability number. One possible upper bound is given by the Lovász theta function, which can be computed as semidefinite program. In order to improve this upper bound, we will add additional constraints to the Lovász theta function, namely exact subgraph constraints. For a certain subgraph, the exact subgraph constraint ensures that the submatrix of the calculation of the Lovász theta function corresponding to the subgraph is contained in the convex hull of all stable set matrices of the subgraph. The talk will give a motivation, why exact subgraph constraints should be considered, address the question of how to choose the subgraphs to be added as exact subgraph constraints and eventually have a look on computational results.




This seminar will give you the opportunity to meet the speaker and all the researchers in attendance while enjoying drinks and snacks. We would highly appreciate if you could confirm your attendance.


Free entrance. Welcome to everyone!


Date

Thursday November 12, 2015
Starts at 15:45

Price

gratuit

Contact

Place

Université de Montréal - Pavillon André-Aisenstadt
2920, chemin de la Tour
Montréal
QC
Canada
H3T 1N8
514 343-6111
4488

Categories