Optimization Online


An Axiomatic Duality Framework for the Theta Body and Related Convex Corners

Marcel de Carli Silva(mksilva***at***ime.usp.br)
Levent Tunçel(ltuncel***at***math.uwaterloo.ca)

Abstract: Lovász 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.

Keywords: semidefinite programming, theta body, chromatic number, stability number

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 12/16/2014
Entry Accepted: 12/16/2014
Entry Last Modified: 12/16/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society