The famous Lovász theta number θ(G) is expressed as the optimal solution of a semidefinite program. As such, it can be computed in polynomial time to an arbitrary precision. Nevertheless, computing it in practice yields some difficulties as the size of the graph gets larger and larger, despite recent significant advances of semidefinite programming (SDP) solvers. We present a way around SDP which exploits a well-known equivalence between SDP and lagrangian relaxations of non-convex quadratic programs. This allows us to design a subgradient algorithm which is shown to be competitive with SDP algorithms in terms of efficiency, while being preferable as far as memory requirements, flexibility and stability are concerned.

Approximating the Lovász θ Function with the Subgradient Method

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

Abstract

The famous Lovász theta number θ(G) is expressed as the optimal solution of a semidefinite program. As such, it can be computed in polynomial time to an arbitrary precision. Nevertheless, computing it in practice yields some difficulties as the size of the graph gets larger and larger, despite recent significant advances of semidefinite programming (SDP) solvers. We present a way around SDP which exploits a well-known equivalence between SDP and lagrangian relaxations of non-convex quadratic programs. This allows us to design a subgradient algorithm which is shown to be competitive with SDP algorithms in terms of efficiency, while being preferable as far as memory requirements, flexibility and stability are concerned.
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/88770
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact