The matching problem is one of the most studied combinatorial optimization problems in the context of extended formulations and convex relaxations. In this paper we provide upper bounds for the rank of the Sum-of-Squares (SoS)/Lasserre hierarchy for a family of matching problems. In particular, we show that when the problem formulation is strengthened by incorporating the objective function in the constraints, the hierarchy requires at most ([)k/2(]) rounds to refute the existence of a perfect matching in an odd clique of size 2k + 1.
展开▼
