Thursday, 13:15 - 13:40 h, Room: H 0104


Monia Giandomenico
An ellipsoidal relaxation for the stable set problem

Coauthors: Adam N. Letchford, Fabrizio Rossi, Stefano Smriglio


A relevant amount of research has been focused on investigating strong relaxations for the stable set problem. In fact, polyhedral combinatorics techniques have been intensively developed since the early seventies in order to strengthen the natural linear formulation. Shortly afterwards, Lovász introduced a celebrated semidefinite programming relaxation, known as theta relaxation. Later on, several attempts to strengthen it by adding linear inequalities have been investigated. The resulting upper bounds turn out to be very strong, but hardly accessible in practice. In this talk, we show that the Lovász theta relaxation can be used to derive a new convex programming relaxation having the same optimal value. Moreover, the new relaxation has a more friendly structure, as its feasible region takes the form of an ellipsoid. We also investigate possible extension of this methodology to stronger relaxations.


Talk 1 of the invited session Thu.2.H 0104
"Strong relaxations for stable set and lot sizing" [...]
Cluster 11
"Integer & mixed-integer programming" [...]


  The system of instant Virginia Payday Loans allows any adult U.S. citizen. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.