On the Lovász theta function and some variants
type: Item
instance of: scholarly article
title: On the Lovász theta function and some variants
zbMATH Open document ID: 1387.90181
author: Laura Galli
author: Adam N. Letchford
published in: Discrete Optimization
publication date: 2018-05-24T00:00:00Z
full work available at URL: theta function.pdf
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 6872143
zbMATH Keywords: stable set problem
zbMATH Keywords: semidefinite programming
zbMATH Keywords: Lovász theta function
describes a project that uses: CSDP
describes a project that uses: DIMACS
MaRDI profile type: Publication
OpenAlex ID: W2613858437
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: On the Shannon capacity of a graph
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Zero knowledge and the chromatic number
cites work: Geometric algorithms and combinatorial optimization
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Computational Experience with Stable Set Relaxations
cites work: On extracting maximum stable sets in perfect graphs using Lovász's theta function
cites work: Semidefinite programming relaxations for graph coloring and maximal clique problems
cites work: Exploring the relationship between max-cut and stable set relaxations
cites work: A comparison of the Delsarte and Lovász bounds
cites work: Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques
cites work: On the facial structure of set packing polyhedra
cites work: Q5687247
cites work: Solving Lift-and-Project Relaxations of Binary Integer Programs
cites work: An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem
cites work: Strong lift-and-project cutting planes for the stable set problem
cites work: A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
cites work: A branch and cut solver for the maximum stable set problem
cites work: A branch-and-cut algorithm for the maximum cardinality stable set problem
cites work: A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
cites work: The Boolean quadratic polytope: Some characteristics, facets and relatives
cites work: Geometry of cuts and metrics
cites work: Q3267900
cites work: CSDP, A C library for semidefinite programming
DOI: 10.1016/J.DISOPT.2017.04.001
description: scientific article; zbMATH DE number 6872143