Approximation of the stability number of a graph via copositive programming

• المؤلفون الرئيسيون: Klerk, Etienne de., Pasechnik, Dmitrii V.
• مؤلفون آخرون: School of Physical and Mathematical Sciences
• التنسيق: مقال
• اللغة: 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...