scientific article
From MaRDI portal
Publication:3002766
DOI10.4086/toc.2006.v002a004zbMath1213.68328OpenAlexW153015188MaRDI 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
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Boolean programming (90C09) Approximation algorithms (68W25) Complexity of proofs (03F20)
Related Items (23)
Rank of random half-integral polytopes — extended abstract — ⋮ Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines ⋮ An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs ⋮ Unnamed Item ⋮ The limits of tractability in resolution-based propositional proof systems ⋮ On polytopes with linear rank with respect to generalizations of the split closure ⋮ Depth lower bounds in Stabbing Planes for combinatorial principles ⋮ Expander graphs and their applications ⋮ Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems ⋮ Towards strong nonapproximability results in the Lovász-Schrijver hierarchy ⋮ Rank bounds for a hierarchy of Lovász and Schrijver ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Cutting Planes and the Parameter Cutwidth ⋮ Cutting planes and the parameter cutwidth ⋮ Resolution Width and Cutting Plane Rank Are Incomparable ⋮ The Complexity of Propositional Proofs ⋮ Exponential Lower Bounds for Polytopes in Combinatorial Optimization ⋮ Convex Relaxations and Integrality Gaps ⋮ Semidefinite and linear programming integrality gaps for scheduling identical machines ⋮ Uncapacitated flow-based extended formulations ⋮ Tight rank lower bounds for the Sherali-Adams proof system ⋮ On the Chvátal rank of the pigeonhole principle ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem
This page was built for publication:
