Publication:3002766
From MaRDI portal
DOI10.4086/toc.2006.v002a004zbMath1213.68328MaRDI QIDQ3002766
Avner Magen, Shlomo Hoory, Toniann Pitassi, Nicola Galesi, Joshua Buresh-Oppenheim
Publication date: 24 May 2011
Published in: Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4086/toc.2006.v002a004
68Q25: Analysis of algorithms and problem complexity
90C05: Linear programming
90C09: Boolean programming
68W25: Approximation algorithms
03F20: Complexity of proofs
Related Items
Unnamed Item, Superlinear Integrality Gaps for the Minimum Majority Problem, The Complexity of Propositional Proofs, The limits of tractability in resolution-based propositional proof systems, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, Rank bounds for a hierarchy of Lovász and Schrijver, Cutting planes and the parameter cutwidth, Uncapacitated flow-based extended formulations, Tight rank lower bounds for the Sherali-Adams proof system, On the Chvátal rank of the pigeonhole principle, Semidefinite and linear programming integrality gaps for scheduling identical machines, Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems, An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Convex Relaxations and Integrality Gaps, Rank of random half-integral polytopes — extended abstract —, Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack, Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines, Expander graphs and their applications, Cutting Planes and the Parameter Cutwidth, Resolution Width and Cutting Plane Rank Are Incomparable
