On the facets of lift-and-project relaxations under graph operations

DOI10.1016/J.DAM.2012.07.012MaRDI QIDQ2448871zbMATHOpenAlexFDO

Authors Néstor E. Aguilera, Pablo G. Fekete, Mariana S. Escalante

Publication date 5 May 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.07.012

zbMATH Keywords

stable setlift-and-project operatorsoperations in graphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Extremal problems in graph theory (05C35) Integer programming (90C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• On the facets of the lift-and-project relaxations of graph subdivisions
• The stable set problem and the lift-and-project ranks of graphs
• On the polyhedral lift-and-project methods and the fractional stable set polytope
• Lift-and-project cuts and perfect graphs
• Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure

Cites work

• A lift-and-project cutting plane algorithm for mixed 0-1 programs
• A new facet generating procedure for the stable set polytope
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Critical facets of the stable set polytope
• Facet Obtaining Procedures for Set Packing Problems
• Further facet generating procedures for vertex packing polytopes
• On the facial structure of set packing polyhedra
• On the polyhedral lift-and-project methods and the fractional stable set polytope
• On the stable set polytope of a series-parallel graph
• Properties of vertex packing and independence system polyhedra
• The stable set problem and the lift-and-project ranks of graphs

Cited in

(6)

• On the polyhedral lift-and-project methods and the fractional stable set polytope
• scientific article; zbMATH DE number 6707767 (Why is no real title available?)
• The stable set problem and the lift-and-project ranks of graphs
• Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
• A comparison between lift-and-project indices and imperfection ratio on web graphs
• On the facets of the lift-and-project relaxations of graph subdivisions

This page was built for publication: On the facets of lift-and-project relaxations under graph operations

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