A Derivation of Lovász' Theta via Augmented Lagrange Duality

DOI10.1051/ro:2003012zbMath1062.90055OpenAlexW2051079209MaRDI QIDQ4809664

Mustapha Ç. Pinar

Publication date: 30 August 2004

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=RO_2003__37_1_17_0

zbMATH Keywords

stable setLagrange dualitysemidefinite relaxationLovász theta function

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Optimality conditions and duality in mathematical programming (90C46) Combinatorial optimization (90C27)

Uses Software

• SDPpack

Cites Work

• Geometric algorithms and combinatorial optimization
• The sandwich theorem
• Connection between semidefinite relaxations of the max-cut and stable set problems
• Nondifferentiable optimization and polynomial problems
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Bounding the Independence Number of a Graph
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
• Fixing Variables in Semidefinite Relaxations

This page was built for publication: A Derivation of Lovász' Theta via Augmented Lagrange Duality