Abstract
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Award date  25 Nov 2013 
Place of Publication  Tilburg 
Publisher  
Print ISBNs  9789056683719 
Publication status  Published  2013 
Fingerprint
Cite this
}
Combinatorial conditions for low rank solutions in semidefinite programming. / Varvitsiotis, A.
Tilburg : CentER, Center for Economic Research, 2013. 168 p.Research output: Thesis › Doctoral Thesis
TY  THES
T1  Combinatorial conditions for low rank solutions in semidefinite programming
AU  Varvitsiotis, A.
PY  2013
Y1  2013
N2  In this thesis we investigate combinatorial conditions that guarantee the existence of lowrank optimal solutions to semidefinite programs. Results of this type are important for approximation algorithms and for the study of geometric representations of graphs. The structure of the thesis is as follows: In Chapter 1 we motivate the study of this problem and sketch the main contributions of the thesis. In Chapters 2, 3 and 4 we give preliminaries on graph theory, semidefinite programming and relaxations of cut polyhedra. In Chapter 5 we study the lowrank positive semidefinite matrix completion problem. Our main tool is a new minor monotone graph parameter, called the Gram dimension of a graph, for which we determine the forbidden minors for values up to 4. Based on this we find that any semidefinite program achieving its optimum, has an optimal solution of rank at most the Gram dimension of its aggregate sparsity pattern. In Chapter 6 we investigate the relation of the Gram dimension with Euclidean graph realizations and a wellknown spectral graph parameter. In Chapter 7 we investigate complexity aspects of the Gram dimension. In Chapter 8 we survey the topic of Grothendieck inequalities and in Chapter 9 we derive a closedform formula for the Grothendieck constant of graphs with noK_5minor. In Chapter 10 we consider semidefinite programs with the unique constraint that every feasible matrix has diagonal entries equal to one. For such semidefinite programs, to prove the existence of lowrank optimal solutions, we introduce a graph parameter called the extreme Gram dimension of a graph. This parameter is upper bounded by the Gram dimension and is closely related to the rankconstrained Grothendieck constant. We show that the extreme Gram dimension is minor monotone and we identify the forbidden minors for graphs with extreme Gram dimension at most 2. Moreover, we show that the extreme Gram dimension is upper bounded by a new treewidthlike parameter, called the strong largeur d’arborescence. In Chapter 11 we determine a sufficient condition for constructing partial positive semidefinite matrices with a unique positive semidefinite completion. Such partial matrices are useful to get lower bounds for the Gram dimension and the extreme Gram dimension. Lastly, we determine interesting connections with the theory of universally rigid graphs.
AB  In this thesis we investigate combinatorial conditions that guarantee the existence of lowrank optimal solutions to semidefinite programs. Results of this type are important for approximation algorithms and for the study of geometric representations of graphs. The structure of the thesis is as follows: In Chapter 1 we motivate the study of this problem and sketch the main contributions of the thesis. In Chapters 2, 3 and 4 we give preliminaries on graph theory, semidefinite programming and relaxations of cut polyhedra. In Chapter 5 we study the lowrank positive semidefinite matrix completion problem. Our main tool is a new minor monotone graph parameter, called the Gram dimension of a graph, for which we determine the forbidden minors for values up to 4. Based on this we find that any semidefinite program achieving its optimum, has an optimal solution of rank at most the Gram dimension of its aggregate sparsity pattern. In Chapter 6 we investigate the relation of the Gram dimension with Euclidean graph realizations and a wellknown spectral graph parameter. In Chapter 7 we investigate complexity aspects of the Gram dimension. In Chapter 8 we survey the topic of Grothendieck inequalities and in Chapter 9 we derive a closedform formula for the Grothendieck constant of graphs with noK_5minor. In Chapter 10 we consider semidefinite programs with the unique constraint that every feasible matrix has diagonal entries equal to one. For such semidefinite programs, to prove the existence of lowrank optimal solutions, we introduce a graph parameter called the extreme Gram dimension of a graph. This parameter is upper bounded by the Gram dimension and is closely related to the rankconstrained Grothendieck constant. We show that the extreme Gram dimension is minor monotone and we identify the forbidden minors for graphs with extreme Gram dimension at most 2. Moreover, we show that the extreme Gram dimension is upper bounded by a new treewidthlike parameter, called the strong largeur d’arborescence. In Chapter 11 we determine a sufficient condition for constructing partial positive semidefinite matrices with a unique positive semidefinite completion. Such partial matrices are useful to get lower bounds for the Gram dimension and the extreme Gram dimension. Lastly, we determine interesting connections with the theory of universally rigid graphs.
M3  Doctoral Thesis
SN  9789056683719
T3  CentER Dissertation Series
PB  CentER, Center for Economic Research
CY  Tilburg
ER 