Lift and project relaxations for the matching and related polytopes

Abstract

We compare lift and project methods given by Lovász and Schrijver (the N+ and N procedures) and by Balas, Ceria and Cornuéjols (the disjunctive procedure) when working on the matching, perfect matching and covering polytopes. When the underlying graph is the complete graph of n=2s+1 nodes we obtain that the disjunctive index for all problems is s2, the N+-index for the matching and perfect matching problems is s (extending a result by Stephen and Tunçel), the N-index for the perfect matching problem is s, and the N+ and N indices for the covering problem and the N-index for the matching problem are strictly greater than s.