An axiomatic duality framework for the theta body and related convex corners

DOI10.1007/s10107-016-1041-3zbMath1421.90108arXiv1412.2103OpenAlexW1554183532MaRDI QIDQ517307

Marcel Kenji De Carli Silva, Tunçel, Levent

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/1412.2103

zbMATH Keywords

semidefinite programmingstability numbercopositive programming(fractional) chromatic numberLovász theta number

Mathematics Subject Classification ID

Semidefinite programming (90C22) Optimality conditions and duality in mathematical programming (90C46) Combinatorial optimization (90C27)

Related Items

A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations ⋮ Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On linear and semidefinite programming relaxations for hypergraph matching
• Entropy splitting for antiblocking corners and perfect graphs
• Copositive programming motivated bounds on the stability and the chromatic numbers
• Lower bounds for measurable chromatic numbers
• Geometric algorithms and combinatorial optimization
• Geometric algorithms and combinatorial optimization.
• On the Shannon capacity of probabilistic graphs
• The sandwich theorem
• Semidefinite programming in combinatorial optimization
• Spectral characterizations of the Lovász number and the Delsarte number of a graph
• The gap between monotone and non-monotone circuit complexity is exponential
• Geometry of homogeneous convex cones, duality mapping, and optimal self-concordant barriers
• Lift-and-project ranks and antiblocker duality
• Optimization problems over unit-distance representations of graphs
• Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
• Lectures on Modern Convex Optimization
• Approximation of the Stability Number of a Graph via Copositive Programming
• Vertices of Spectrahedra arising from the Elliptope, the Theta Body, and Their Relatives
• Theta Bodies for Polynomial Ideals
• The Operator $\Psi$ for the Chromatic Number of a Graph
• Approximate graph coloring by semidefinite programming
• A comparison of the Delsarte and Lovász bounds
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• Barrier Functions in Interior Point Methods
• Continuous Characterizations of the Maximum Clique Problem
• The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
• A Convex Quadratic Characterization of the Lovász Theta Number
• Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
• A Generalization of the Perfect Graph Theorem Under the Disjunctive Index
• Note On: N. E. Aguilera, M. S. Escalante, G. L. Nasini, “A Generalization of the Perfect Graph Theorem Under the Disjunctive Index”
• Quadratic forms on graphs

This page was built for publication: An axiomatic duality framework for the theta body and related convex corners