  


Forbidden minor characterizations for lowrank optimal solutions to semidefinite programs over the elliptope
Marianna EisenbergNagy (M.E.Nagycwi.nl) Abstract: We study a new geometric graph parameter $\egd(G)$, defined as the smallest integer $r\ge 1$ for which any partial symmetric matrix which is completable to a correlation matrix and whose entries are specified at the positions of the edges of $G$, can be completed to a matrix in the convex hull of correlation matrices of $\rank $ at most $r$. This graph parameter is motivated by its relevance to the problem of finding low rank solutions to semidefinite programs over the elliptope, and also by its relevance to the bounded rank Grothendieck constant. Indeed, $\egd(G)\le r$ if and only if the rank$r$ Grothendieck constant of $G$ is equal to 1. We show that the parameter $\egd(G)$ is minor monotone, we identify several classes of forbidden minors for $\egd(G)\le r$ and we give the full characterization for the case $r=2$. We also show an upper bound for $\egd(G)$ in terms of a new treewidthlike parameter $\sla(G)$, defined as the smallest $r$ for which $G$ is a minor of the strong product of a tree and $K_r$. We show that, for any 2connected graph $G\ne K_{3,3}$ on at least 6 nodes, $\egd(G)\le 2$ if and only if $\sla(G)\le 2$. Keywords: matrix completion, semidefinite programming, correlation matrix, Gram representation, graph minor, treewidth, Grothendieck constant Category 1: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Category 2: Combinatorial Optimization (Graphs and Matroids ) Citation: 33 pages, 8 Figures. In its second version, the paper has been modified to accommodate the suggestions of the referees. Furthermore, the title has been changed since we feel that the new title reflects more accurately the content and the main results of the paper Download: [PDF] Entry Submitted: 05/09/2012 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  