An axiomatic duality framework for the theta body and related convex corners
From MaRDI portal
Publication:517307
Abstract: Lovasz theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information theory, and semidefinite optimization. In this paper, utilizing a modern convex optimization viewpoint, we provide a set of minimal conditions (axioms) under which certain key, desired properties are generalized, including the main equivalent characterizations of the theta function, the theta body of graphs, and the corresponding antiblocking duality relations. Our framework describes several semidefinite and polyhedral relaxations of the stable set polytope of a graph as generalized theta bodies. As a by-product of our approach, we introduce the notion of "Schur Lifting" of cones which is dual to PSD Lifting (more commonly used in SDP relaxations of combinatorial optimization problems) in our axiomatic generalization. We also generalize the notion of complements of graphs to diagonally scaling-invariant polyhedral cones. Finally, we provide a weighted generalization of the copositive formulation of the fractional chromatic number by Dukanovic and Rendl.
The authors use a modern convex optimization viewpoint to provide a set of minimal conditions under which certain desired important properties, including the main equivalent charactersizations of the theta function, the theta body of graphs and the corresponding antiblocking realtions, are generalized. The framework of this paper describes several semidefinite and polyhedral relaxations of the stable set polytope of a graph as generalized theta bodies. The authors also generalize the notion of complements of graphs to diagonally scaling-invariant polyhedral cones.
Recommendations
- A characterization of the duality mapping for convex bodies
- Duality of convex bodies
- Dual representations of convex bodies and their polars
- The concept of duality for measure projections of convex bodies
- A Refinement of Van Der Corput's Theorem on Convex Bodies
- Polar Duals of Convex Bodies
- scientific article; zbMATH DE number 1117756
- scientific article; zbMATH DE number 5556571
- The dual Minkowski problem for symmetric convex bodies
- DUALITY FOR CONVEX POLYTOPES
Cites work
- A comparison of the Delsarte and Lovász bounds
- A Convex Quadratic Characterization of the Lovász Theta Number
- A Generalization of the Perfect Graph Theorem Under the Disjunctive Index
- Approximate graph coloring by semidefinite programming
- Approximation of the stability number of a graph via copositive programming
- Barrier Functions in Interior Point Methods
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Continuous Characterizations of the Maximum Clique Problem
- Copositive programming motivated bounds on the stability and the chromatic numbers
- Entropy splitting for antiblocking corners and perfect graphs
- Geometric algorithms and combinatorial optimization
- Geometric algorithms and combinatorial optimization.
- Geometry of homogeneous convex cones, duality mapping, and optimal self-concordant barriers
- scientific article; zbMATH DE number 4035938 (Why is no real title available?)
- scientific article; zbMATH DE number 47926 (Why is no real title available?)
- scientific article; zbMATH DE number 3634289 (Why is no real title available?)
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1943970 (Why is no real title available?)
- scientific article; zbMATH DE number 3349875 (Why is no real title available?)
- Integer Decomposition for Polyhedra Defined by Nearly Totally Unimodular Matrices
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Lift-and-project ranks and antiblocker duality
- Lower bounds for measurable chromatic numbers
- Note On: N. E. Aguilera, M. S. Escalante, G. L. Nasini, “A Generalization of the Perfect Graph Theorem Under the Disjunctive Index”
- On linear and semidefinite programming relaxations for hypergraph matching
- On the Shannon capacity of a graph
- On the Shannon capacity of probabilistic graphs
- Optimization problems over unit-distance representations of graphs
- Perfect graphs and graph entropy: An updated survey
- Quadratic forms on graphs
- Semidefinite programming in combinatorial optimization
- Spectral characterizations of the Lovász number and the Delsarte number of a graph
- Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
- The gap between monotone and non-monotone circuit complexity is exponential
- The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
- The Operator \Psi for the Chromatic Number of a Graph
- The sandwich theorem
- The theta body and imperfection
- Theta bodies for polynomial ideals
- Vertices of spectrahedra arising from the elliptope, the theta body, and their relatives
Cited in
(4)- Vertices of spectrahedra arising from the elliptope, the theta body, and their relatives
- Theta bodies for polynomial ideals
- Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming
- A notion of total dual integrality for convex, semidefinite, and extended formulations
This page was built for publication: An axiomatic duality framework for the theta body and related convex corners
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517307)
