Paper Info
Title
An application of the Lovász–Schrijver M(K, K) operator to the stable set problem
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.
Year
DOI
Venue
2009
10.1007/s10107-008-0219-8
Math. Program.
Keywords
Field
DocType
resulting relaxation,stable set problem,initial linear programming,semidefinite programming technique,extensive computational result,lift-and-project operator,intense study,lovász-schrijver operators · stable set problem · semidefinite programming,schrijver m,stronger extended lp relaxation,effective practical implementation,non-negativity inequality,projection operator,upper bound,stable set,lp relaxation
Discrete mathematics,Mathematical optimization,Combinatorics,Clique,Upper and lower bounds,Combinatorial optimization,Independent set,Linear programming,Operator (computer programming),Linear programming relaxation,Mathematics,Semidefinite programming
Journal
Volume
Issue
ISSN
120
2
1436-4646
Citations 
PageRank 
References 
8
0.50
20
Authors
4
Name
Order
Citations
PageRank
Monia Giandomenico1303.74
Adam N. Letchford267154.97
Fabrizio Rossi314016.33
Stefano Smriglio415314.81