Paper Info
Title
Sherali-adams relaxations of the matching polytope
Abstract
We study the Sherali-Adams lift-and-project hierarchy of linear programming relaxations of the matching polytope. Our main result is an asymptotically tight expression 1+1/k for the integrality gap after k rounds of this hierarchy. The result is derived by a detailed analysis of the LP after k rounds applied to the complete graph K_{2d+1}. We give an explicit recurrence for the value of this LP, and hence show that its gap exhibits a "phase transition," dropping from close to its maximum value 1+1/2d to close to 1 around the threshold k=2d-Θ(√d). We also show that the rank of the matching polytope (i.e., the number of Sherali-Adams rounds until the integer polytope is reached) is exactly 2d-1.
Year
DOI
Venue
2009
10.1145/1536414.1536456
STOC
Keywords
Field
DocType
maximum value,main result,integrality gap,sherali-adams round,threshold k,sherali-adams relaxation,k round,asymptotically tight expression,sherali-adams lift-and-project hierarchy,integer polytope,matching polytope,phase transition,complete graph,linear programming relaxation,maximum matching
Integer,Discrete mathematics,Complete graph,Birkhoff polytope,Combinatorics,Matching (graph theory),Polytope,Linear programming,Linear programming relaxation,Hierarchy,Mathematics
Conference
ISSN
Citations 
PageRank 
0737-8017
25
0.85
References 
Authors
23
2
Name
Order
Citations
PageRank
Claire Mathieu145225.78
Alistair Sinclair21506308.40