Semidefinite Programming Approaches for Structured Combinatorial Optimization Problems


Update content

Title Semidefinite Programming Approaches for Structured Combinatorial Optimization Problems
Period 01 / 2006 - 03 / 2011
Status Completed
Dissertation Yes
Research number OND1315370
Data Supplier METIS Universiteit van Tilburg


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.

Related organisations

Related people

Supervisor Prof.dr. E. de Klerk
Doctoral/PhD student Dr. C. Dobre


D70000 Economics and Business Administration

Go to page top
Go back to contents
Go back to site navigation