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, Lovasz 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 Lovasz 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.

A branch-and-cut for the stable set problem based on an ellipsoidal relaxation

ROSSI, FABRIZIO;SMRIGLIO, STEFANO
2012-01-01

Abstract

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, Lovasz 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 Lovasz 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/88648
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact