Tree-width and the Sherali-Adams operator

DOI10.1016/j.disopt.2004.03.002zbMath1154.90548OpenAlexW2080394239MaRDI QIDQ2386210

Nuri Özbay, Bienstock, Daniel

Publication date: 22 August 2005

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2004.03.002

zbMATH Keywords

integer programmingcombinatorial optimization

Mathematics Subject Classification ID

Trees (05C05) Integer programming (90C10) Combinatorial optimization (90C27)

Related Items (19)

PEBBLE GAMES AND LINEAR EQUATIONS ⋮ Max-Cut Under Graph Constraints ⋮ A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ Exploiting sparsity for the min \(k\)-partition problem ⋮ Tightening simple mixed-integer sets with guaranteed bounds ⋮ Extended formulation for CSP that is compact for instances of bounded treewidth ⋮ LP Formulations for Polynomial Optimization Problems ⋮ Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra ⋮ Approximate formulations for 0-1 knapsack sets ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs ⋮ Unnamed Item ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ Approximating graph-constrained max-cut ⋮ On the polyhedral lift-and-project methods and the fractional stable set polytope ⋮ Worst-case analysis of clique MIPs ⋮ Approximate fixed-rank closures of covering problems ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side ⋮ New limits of treewidth-based tractability in optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A class of facet producing graphs for vertex packing polyhedra
• Wheel inequalities for stable set polytopes
• The stable set problem and the lift-and-project ranks of graphs
• Antiweb-wheel inequalities and their separation problems over the stable set polytopes
• On the Matrix-Cut Rank of Polyhedra
• Tour Merging via Branch-Decomposition
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Generalizations of Cliques, Odd Cycles and Anticycles and Their Relation to Independence System Polyhedra
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Disjunctive Programming
• Branch decompositions and minor containment
• Transitive packing
• Subset Algebra Lift Operators for 0-1 Integer Programming
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• On the rank of mixed 0,1 polyhedra.

This page was built for publication: Tree-width and the Sherali-Adams operator