Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-003 | 13th December 2011 19:00

Rank Bounds for a Hierarchy of Lov\'{a}sz and Schrijver


Authors: Pratik Worah
Publication: 6th January 2012 13:59
Downloads: 1268


Lov\'{a}sz and Schrijver introduced several lift and project methods for $0$-$1$ integer programs, now collectively known as Lov\'{a}sz-Schrijver ($LS$) hierarchies. Several lower bounds have since been proven for the rank of various linear programming relaxations in the $LS$ and $LS_+$ hierarchies. In this paper we investigate rank bounds in the more general $LS_*$ hierarchy, which allows lifts by any derived inequality as opposed to just $x\ge 0$ and $1-x\ge 0$ in the $LS$ hierarchy. Rank lower bounds for $LS_*$ were obtained for the symmetric knapsack polytope by Grigoriev et al. In this paper we show that $LS_*$ rank is incomparable to other hierarchies like $LS_+$ and Sherali-Adams ($SA$) and show rank lower bounds for $PHP_n^{n+1}$ and integrality gaps for optimization problems like MAX-CUT in $LS_*$. The rank lower bounds for $LS_*$ follow from rank lower bounds for the $SA_*$ hierarchy which is a generalization of the $SA$ hierarchy in the same vein as $LS_*$.

We show that the $LS_*$ rank of $PHP_n^{n+1}$ is $\sim\log_2n$. We also extend the polynomial rank lower bounds and integrality gaps for MAX-CUT studied in Charikar et al. for $SA$ hierarchy to corresponding logarithmic rank lower bounds and integrality gaps in the $LS_*$ hierarchy. The proof translates various known $SA$ rank lower bounds in Charikar et al. to weaker $SA_*$ (and $LS_*$) rank lower bounds as long as the number of variables in the constraints of the initial linear program is small. In the reverse direction we give an example of a linear program with large number of variables in a constraint which has unit rank in $SA_*$ (and $LS_*$) hierarchies but linear rank in $SA$ (and $LS_+$) hierarchies.

ISSN 1433-8092 | Imprint