scientific article

zbMath1302.90176MaRDI QIDQ2934582

Claire Kenyon-Mathieu, Wenceslas Fernandez de la Vega

Publication date: 18 December 2014

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (26)

On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Sherali-Adams Relaxations for Valued CSPs ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Integrality gaps for colorful matchings ⋮ A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems ⋮ Unnamed Item ⋮ Towards strong nonapproximability results in the Lovász-Schrijver hierarchy ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ Improved Approximation Guarantees through Higher Levels of SDP Hierarchies ⋮ Rank bounds for a hierarchy of Lovász and Schrijver ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ Unnamed Item ⋮ 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 − ɛ ⋮ Sherali-adams strikes back ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem

This page was built for publication: