Publication:3549626
From MaRDI portal
zbMath1232.90303MaRDI QIDQ3549626
Luca Trevisan, Madhur Tulsiani, Grant Schoenebeck
Publication date: 5 January 2009
90C05: Linear programming
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Superlinear Integrality Gaps for the Minimum Majority Problem, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ, Sherali-adams strikes back, The Power of Sherali--Adams Relaxations for General-Valued CSPs, Unnamed Item, Integrality gaps for strengthened linear relaxations of capacitated facility location, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, Uncapacitated flow-based extended formulations, Semidefinite and linear programming integrality gaps for scheduling identical machines, Lift \& project systems performing on the partial-vertex-cover polytope, Sherali-Adams relaxations of graph isomorphism polytopes, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Convex Relaxations and Integrality Gaps, Hypercontractive inequalities via SOS, and the Frankl--Rödl graph, Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack, Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines, Approximation Limits of Linear Programs (Beyond Hierarchies), Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
