Approximation of the stability number of a graph via copositive programming

• Main Authors: Klerk, Etienne de., Pasechnik, Dmitrii V.
• 其他作者: School of Physical and Mathematical Sciences
• 格式: Article
• 語言: English
• 出版: 2011
• 主題: DRNTU::Science::Mathematics::Applied mathematics
• 在線閱讀: https://hdl.handle.net/10356/93758; http://hdl.handle.net/10220/6790
• 機構: 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...