Optimization Online


Min-Max Theorems Related to Geometric Representations of Graphs and their SDPs

Marcel K. de Carli Silva (mksilva***at***math.uwaterloo.ca)
Levent Tuncel (ltuncel***at***math.uwaterloo.ca)

Abstract: Lovasz proved a nonlinear identity relating the theta number of a graph to its smallest radius hypersphere embedding where each edge has unit length. We use this identity and its generalizations to establish min-max theorems and to translate results related to one of the graph invariants above to the other. Classical concepts in tensegrity theory allow good interpretations of the dual SDP for the problem of finding an optimal hypersphere embedding as above. We generate a spectrum of structured SDPs on which extensions of such interpretations are possible.

Keywords: geometric representations of graphs, semidefinite programming, Lovasz theta number, duality theory

Category 1: Combinatorial Optimization

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Research Report, October 2010

Download: [PDF]

Entry Submitted: 10/29/2010
Entry Accepted: 10/30/2010
Entry Last Modified: 08/08/2011

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