12,000

We have over 12,000 students, from over 100 countries, within one of the safest campuses in the UK

93%

93% of Lancaster students go into work or further study within six months of graduating

Home > Research > Publications & Outputs > An application of the Lovasz-Schrijver M(K,K) o...
View graph of relations

« Back

An application of the Lovasz-Schrijver M(K,K) operator to the stable set problem

Research output: Contribution to journalJournal article

Published

Journal publication date2009
JournalMathematical Programming
Journal number2
Volume120
Number of pages21
Pages381-401
Original languageEnglish

Abstract

Although the lift-and-project operators of Lovász and Schrijver have been the subject of intense study, their M(K, K) operator has received little attention. We consider an application of this operator to the stable set problem. We begin with an initial linear programming (LP) relaxation consisting of clique and non-negativity inequalities, and then apply the operator to obtain a stronger extended LP relaxation. We discuss theoretical properties of the resulting relaxation, describe the issues that must be overcome to obtain an effective practical implementation, and give extensive computational results. Remarkably, the upper bounds obtained are sometimes stronger than those obtained with semidefinite programming techniques.