Approximation of the stability number of a graph via copositive programming

• Main Authors: Klerk, Etienne de., Pasechnik, Dmitrii V.
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2011
• Subjects: DRNTU::Science::Mathematics::Applied mathematics
• Online Access: https://hdl.handle.net/10356/93758; http://hdl.handle.net/10220/6790
• Institution: Nanyang Technological University

Lovász and Schrijver [SIAM J. Optim., 1 (1991), pp. 166–190] showed how to formulate increasingly tight approximations of the stable set polytope of a graph by solving semidefinite programs (SDPs) of increasing size (lift-and-project method). In this paper we present a similar idea. We show how the s...