scientific article
From MaRDI portal
Publication:3549626
zbMath1232.90303MaRDI QIDQ3549626
Luca Trevisan, Madhur Tulsiani, Grant Schoenebeck
Publication date: 5 January 2009
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (19)
Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Towards strong nonapproximability results in the Lovász-Schrijver hierarchy ⋮ Improved Approximation Guarantees through Higher Levels of SDP Hierarchies ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ 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 ⋮ No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ ⋮ Hypercontractive inequalities via SOS, and the Frankl--Rödl graph ⋮ Sherali-adams strikes back ⋮ Sherali-Adams relaxations of graph isomorphism polytopes ⋮ Unnamed Item ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem
This page was built for publication: