Nebojša Gvozdenović will receive his PhD degree for the research he carried out at CWI. He will defend his thesis entitled Approximating the Stability Number and the Chromatic Number of a Graph via Semidefinite Programming on 10 April 2008 at the University of Amsterdam.
Gvozdenović investigated two hard combinatorial optimization problems concerning graphs. A graph consists of vertices, of which some are connected by edges. A stable set is a set of vertices of a graph in which no two of them are connected with an edge. Assignment of colours to the vertices of a graph, such that no two connected vertices share the same colour, is called a vertex colouring. One is usually interested in finding a maximum-size stable set or a vertex colouring which uses the least possible number of colours.
Some practical problems, like time tabling, scheduling, phone frequency assignment and register allocation can be modelled as stable set or colouring problems. In the assignment of cell phone frequencies, the vertices are transmitting stations. They are connected by an edge when they are near each other. The least possible number of colours is now the minimal number of frequencies that is necessary to communicate without interference. No fast solution method is known for these kinds of problems and some people even think that there is no solution.
Gvozdenović studied a new approach to the problem. He developed a method to find better bounds for the number of colours or the size of a stable set. With this method he provided solutions to several hard problems.
This research is part of the NWO-VIDI project of Monique Laurent, Semidefinite Programming and Combinatorial Optimization.
After receiving his PhD Gvozdenović returns to Serbia where he accepted a position at the University of Novi Sad. There he will teach and will be involved in research projects at the Faculty of Economics. More personal information can be found on his university website.
