Outer approximation for semidefinite programs and a vector clock problem

 In this thesis, we study linear outer approximations of semidefinite programs (SDPs) and extend these ideas to build algorithms that solve binary SDPs arising from quadratically constrained quadratic binary problems. We conclude by introducing a multi-commodity vector clock problem and deriving a structural result for it. 

Chapter 1 introduces our generic technique to obtain linear relaxations of semidefinite programs with provable guarantees based on the commutativity of the constraint and the objective matrices. We study conditions under which the optimal value of the SDP and the proposed linear relaxation match, which we then relax to provide a flexible methodology to derive strong linear relaxations. 

Chapter 2 introduces a spectral second-order outer approximation algorithm to solve to optimality integer semidefinite programs that are themselves exact formulations of binary quadratically constrained quadratic problems. Our approach fundamentally builds on the results of the previous chapter. 

Chapter 3 considers rumor spreading problems in undirected graphs, generalizing the minimum broadcast time problem to the multi-commodity case. We also consider its extension to an infinite horizon version to minimize information latencies captured in a vector clock model. We show that the multi-commodity version of these problems on general graphs have locally periodic schedules that are within a poly-logarithmic factor of optimal by studying the properties of a non convex relaxation.