Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
From MaRDI portal
Publication:517302
DOI10.1007/s10107-016-1035-1zbMath1380.90268arXiv1411.2069OpenAlexW1803930816MaRDI QIDQ517302
Publication date: 23 March 2017
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1411.2069
semidefinite programmingcombinatorial optimizationstable set problemlift and project methodsinteger programming.
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Integer programming (90C10) Combinatorial optimization (90C27)
Related Items
Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs, Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
Cites Work
- Strong lift-and-project cutting planes for the stable set problem
- Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
- The strong perfect graph theorem
- Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture
- Critical facets of the stable set polytope
- Semidefinite bounds for the stability number of a graph via sums of squares of polynomials
- On the polyhedral lift-and-project methods and the fractional stable set polytope
- The ellipsoid method and its consequences in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- Near-perfect matrices
- On certain polytopes associated with graphs
- Progress on perfect graphs
- The stable set problem and the lift-and-project ranks of graphs
- Tighter representations for set partitioning problems
- Applying Lehman's theorems to packing problems
- Tree-width and the Sherali-Adams operator
- An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem
- On the facets of lift-and-project relaxations under graph operations
- Recognizing Berge graphs
- Approximation of the Stability Number of a Graph via Copositive Programming
- Some advances on Lovász-Schrijver relaxations of the fractional stable set polytope
- Near-perfect graphs with polyhedral
- Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Further facet generating procedures for vertex packing polytopes
- On the Shannon capacity of a graph
- On the facial structure of set packing polyhedra
- Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
