Rank bounds for a hierarchy of Lovász and Schrijver

Pratik Worah ()
Additional contact information
Pratik Worah: Courant Institute of Mathematical Sciences

Journal of Combinatorial Optimization, 2015, vol. 30, issue 3, No 18, 689-709

Abstract: Abstract Lovász and Schrijver introduced several lift and project methods for 0–1 integer programs, now collectively known as Lovász–Schrijver (LS) hierarchies. Several lower bounds have since been proven for the rank of various linear programming relaxations in the LS and $$\hbox {LS}_+$$ LS + hierarchies. We investigate rank bounds in the more general $$\hbox {LS}_*$$ LS ∗ hierarchy, which allows lifts by any derived inequality as opposed to just $$x\ge 0$$ x ≥ 0 and $$1-x\ge 0$$ 1 - x ≥ 0 in the LS hierarchy. Rank lower bounds for $$\hbox {LS}_*$$ LS ∗ were obtained for the symmetric knapsack polytope by Grigoriev et al. We reinitiate further investigation into such general lifts. We prove simple upper bounds on rank which show that under such general lifts one can potentially converge to the integer solution much faster than $$\hbox {LS}_+$$ LS + or Sherali–Adams (SA) hierarchy. This motivates our investigation of rank lower bounds and integrality gaps for $$\hbox {LS}_*$$ LS ∗ and the $$\hbox {SA}_*$$ SA ∗ hierarchy, the latter is a generalization of the SA hierarchy in the same vein as $$\hbox {LS}_*$$ LS ∗ . In particular, we show that the $$\hbox {LS}_*$$ LS ∗ rank of $$PHP_n^{n+1}$$ P H P n n + 1 is $$\sim \log _2n$$ ∼ log 2 n . We also extend the rank lower bounds and integrality gaps for SA hierarchy to the $$\hbox {LS}_*$$ LS ∗ and $$\hbox {SA}_*$$ SA ∗ hierarchies as long as the maximum number of variables in any constraint of the initial linear program is bounded by a constant.

Keywords: Linear programming; Integrality gaps; Proof complexity (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9662-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:3:d:10.1007_s10878-013-9662-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9662-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().