文章基本信息

标题：Rank Bounds for a Hierarchy of Lov\'{a}sz and Schrijver
本地全文：下载
作者：Pratik Worah
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 x0 and 1−x0 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 PHPnn+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 PHPnn+1 is log2n. 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.
关键词：Geometric Proof Systems, Integrality gaps