Tree-width and the Sherali-Adams operator

DOI10.1016/J.DISOPT.2004.03.002MaRDI QIDQ2386210zbMATH OpenOpenAlexFDO

Authors Daniel Bienstock, Nuri Özbay

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

combinatorial optimizationinteger programming

Mathematics Subject Classification ID

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

Recommendations

• The Dirichlet spectral radius of trees
• Generalized Schur operators on planar binary trees
• Estimates for n-widths of two-weighted summation operators on trees
• On the spectral radius of trees
• Tree-width in algebraic complexity
• Potential theory on trees and multiplication operators
• A Menger-like property of tree-width: The finite case
• On the Laplacian spectral radius of trees
• Self-adjointness and limit pointness for adjacency operators on a tree
• A note on spectral radius of trees

Cites work

• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 1757962 (Why is no real title available?)
• scientific article; zbMATH DE number 876684 (Why is no real title available?)
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A class of facet producing graphs for vertex packing polyhedra
• Antiweb-wheel inequalities and their separation problems over the stable set polytopes
• Branch decompositions and minor containment
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Disjunctive Programming
• Easy problems for tree-decomposable graphs
• Generalizations of Cliques, Odd Cycles and Anticycles and Their Relation to Independence System Polyhedra
• Graph minors. II. Algorithmic aspects of tree-width
• On the matrix-cut rank of polyhedra.
• On the rank of mixed 0,1 polyhedra.
• Subset Algebra Lift Operators for 0-1 Integer Programming
• The stable set problem and the lift-and-project ranks of graphs
• Tour merging via branch-decomposition
• Transitive packing
• Wheel inequalities for stable set polytopes
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?

Cited in

(20)

• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
• On the polyhedral lift-and-project methods and the fractional stable set polytope
• Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time
• Tightening simple mixed-integer sets with guaranteed bounds
• Integrality gaps of linear and semi-definite programming relaxations for knapsack
• Approximating graph-constrained max-cut
• Approximate formulations for 0-1 knapsack sets
• Bilu-Linial stability, certified algorithms and the independent set problem
• Extended formulation for CSP that is compact for instances of bounded treewidth
• Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra
• Approximate fixed-rank closures of covering problems
• LP formulations for polynomial optimization problems
• Exploiting sparsity for the min \(k\)-partition problem
• Max-cut under graph constraints
• New limits of treewidth-based tractability in optimization
• PEBBLE GAMES AND LINEAR EQUATIONS
• The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
• On linear and semidefinite programming relaxations for hypergraph matching
• Worst-case analysis of clique MIPs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2386210)