Home > Research > Publications & Outputs > Approximating the Lovász θ function with the su...

Associated organisational unit


Text available via DOI:

View graph of relations

Approximating the Lovász θ function with the subgradient method

Research output: Contribution to Journal/MagazineJournal articlepeer-review

<mark>Journal publication date</mark>5/06/2013
<mark>Journal</mark>Electronic Notes in Discrete Mathematics
Number of pages8
Pages (from-to)157-164
Publication StatusPublished
<mark>Original language</mark>English


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.