TY - JOUR

T1 - Approximating the Lovász θ function with the subgradient method

AU - Giandomenico, Monia

AU - Letchford, Adam N.

AU - Rossi, Fabrizio

AU - Smriglio, Stefano

PY - 2013/6/5

Y1 - 2013/6/5

N2 - 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.

AB - 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.

KW - Lagrangian relaxation

KW - Maximum stable set

KW - Quadratic programming

KW - Subgradient method

U2 - 10.1016/j.endm.2013.05.088

DO - 10.1016/j.endm.2013.05.088

M3 - Journal article

AN - SCOPUS:84879727104

VL - 41

SP - 157

EP - 164

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

SN - 1571-0653

ER -