Kleuren met semidefiniete optimalisering
11 april 2008
Wiskundige Nebojsa Gvozdenovic promoveerde donderdag 10 april aan de
Universiteit van Amsterdam. Op het CWI deed Gvozdenovic onderzoek naar
nieuwe technieken moeilijke problemen uit de combinatorische
optimalisering op te lossen. Toepassingen zijn bijvoorbeeld het maken
van schoolroosters, de verdeling van radio- of telefoonfrequenties en
het toewijzen van gates aan vliegtuigen.
Grafen spelen de hoofdrol in het modelleren van problemen uit de
combinatorische optimalisering. Een graaf bestaat uit punten, waarvan
sommige zijn verbonden door lijnen. Een verzameling punten is
'onafhankelijk' als deze punten onderling niet verbonden zijn door een
lijn. Bij de verdeling van telefoonfrequenties zijn de punten van de
graaf bijvoorbeeld de GSM zendmasten. Er staat een lijn tussen twee
zendmasten als ze dicht bij elkaar liggen en dus niet dezelfde
frequentie kunnen gebruiken. De masten die ver uit elkaar staan en dus
niet verbonden zijn met een lijn, vormen een onafhankelijke
verzameling die allemaal dezelfde frequentie kunnen gebruiken. Door de
punten van de graaf een kleur toe te wijzen op zo'n manier dat de
eindpunten van elke lijn een verschillende kleur hebben, kan de mate
van overlap tussen de punten aangegeven worden. Hoe meer kleuren, hoe
vaker de punten met elkaar verbonden zijn. In het geval van de
telefoonfrequenties betekent dit dus dat het aantal verschillende
kleuren aangeeft hoeveel frequenties er minimaal gebruikt moeten
worden om zonder storing te communiceren. Men is geïnteresseerd in het
vinden van een maximale onafhankelijke verzameling van punten en een
puntkleuring met een minimaal aantal kleuren. Voor zulke problemen
zijn geen efficiënte algoritmen bekend en veel mensen denken dat zo'n
algoritme zelfs niet bestaat.
Gvozdenovic bestudeerde een nieuwe aanpak om het probleem efficiënt te
benaderen. Hij ontwikkelde een systematische methode waarmee hij
steeds betere grenzen kan vinden voor het aantal kleuren of de grootte
van onafhankelijke verzamelingen. Hiermee was hij in staat om betere
oplossingen te vinden voor bekende lastige problemen.
Het onderzoek van Gvozdenovic valt onder het NWO-project 'Semidefinite
Programming and Combinatorial Optimization' van Vidi Monique Laurent.
..............................
Meer informatie bij:
* dr. Monique Laurent (Centrum voor Wiskunde en Informatica)
* t. +31(0)20 592 4105 M.Laurent@cwi.nl
* promotie: 10 april
* promotor(en): prof. dr. A. schrijver, co-promotor: dr. M. Laurent
* http://db.cwi.nl/projecten/project.php4?prjnr=200
Nederlandse Organisatie voor Wetenschappelijk Onderzoek