On the Lovász theta function and some variants
From MaRDI portal
Publication:1751239
DOI10.1016/j.disopt.2017.04.001zbMath1387.90181OpenAlexW2613858437MaRDI QIDQ1751239
Laura Galli, Adam N. Letchford
Publication date: 24 May 2018
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/85914/1/theta_function.pdf
Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Mathematical Programming Models and Exact Algorithms, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Strong lift-and-project cutting planes for the stable set problem
- A branch and cut solver for the maximum stable set problem
- Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- The Boolean quadratic polytope: Some characteristics, facets and relatives
- The ellipsoid method and its consequences in combinatorial optimization
- Geometric algorithms and combinatorial optimization
- Zero knowledge and the chromatic number
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem
- Exploring the relationship between max-cut and stable set relaxations
- On extracting maximum stable sets in perfect graphs using Lovász's theta function
- A comparison of the Delsarte and Lovász bounds
- Cones of Matrices and Set-Functions and 0–1 Optimization
- A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
- On the Shannon capacity of a graph
- Computational Experience with Stable Set Relaxations
- CSDP, A C library for semidefinite programming
- On the facial structure of set packing polyhedra
- Solving Lift-and-Project Relaxations of Binary Integer Programs
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Geometry of cuts and metrics
- A branch-and-cut algorithm for the maximum cardinality stable set problem
