CentER

Cristian Dobre

Date of PhD defense:	18 March 2011
Title of thesis:	Semidefinite Programming Approaches for Structured Combinatorial Optimization Problems
ISBN:	978 90 5668 271 2
Promotor:	Prof.dr. Etienne de Klerk

Abstract:
This thesis contains applications of semidefinite programming (SDP) for combinatorial optimization problems such as computing the crossing number of a graph, computing the clique number of a graph, solving a travelling salesman problem, or finding a maximum equipartition, all of which are known to be NP-hard. That is, there exists no polynomial-time algorithm that can solve these problems to optimality, unless P=NP. Therefore, approximating their optimal solution in polynomial time is an important goal. New techniques have been developed in the last thirty years using semidefinite programming approaches. However, the SDPs involved are often very large and the size of the problems that can be solved is still limited. A recurrent difficulty in applying interior point methods is that it is more difficult to exploit special structure in the data in the SDP case than in the linear programming (LP) case. In particular, sparsity may be readily exploited by interior point methods in LP, but this is not true for SDP. This thesis presents results on exploiting symmetry in the data of SDP relaxations for the combinatorial optimization problems described above.

Full text