A structural approach to constraint satisfaction problems
| Promotie: | M. Medema, MSc |
| Wanneer: | 01 april 2025 |
| Aanvang: | 12:45 |
| Promotors: | A. (Alexander) Lazovik, Prof, prof. dr. M. Aiello |
| Waar: | Academiegebouw RUG |
| Faculteit: | Science and Engineering |
Een structurele benadering voor constraint satisfaction problemen
Een groot aantal problemen, variërend van plannen en roosteren tot het nemen van autonome beslissingen in smart environments, kan worden gemodelleerd als constraint satisfaction problems (CSP's). Hoewel dit generieke framework het mogelijk maakt om veel verschillende problemen met dezelfde algoritmes op te lossen, zorgt het feit dat CSP’s NP-volledige problemen zijn ervoor dat deze algoritmes een exponentiële computationele complexiteit hebben.
Dit beperkt de grootte van een probleem aanzienlijk, omdat het tijdig vinden van een oplossing voor vrijwel alle toepassingen is vereist. Ondanks de NP-volledigheid kunnen CSP’s in de praktijk echter veelal efficiënt worden opgelost, wat deze exponentiële tijdscomplexiteit weinig informatief maakt. Op basis van de structuur van een probleem en de zoekruimte zijn problemen geïdentificeerd die in polynomiale tijd opgelost kunnen worden en zoektechnieken ontworpen met betere theoretische eigenschappen. De tijdscomplexiteit van dit soort algoritmes is helaas niet veel informatiever, en gebruik maken van deze structuren vormt een uitdaging omdat er geen efficiënte algoritmes bestaan voor hieraan gerelateerde taken.
In zijn proefschrift onderzoekt Michel Medema de structuur van CSP’s en de zoekruimte en op welke manier deze de zoektijd van algoritmes beïnvloedt. Dat geeft nieuwe inzichten in de tijdscomplexiteit en daadwerkelijke efficiëntie van algoritmes, wat bijvoorbeeld kan helpen bij het selecteren van het beste algoritme voor een bepaald probleem en het ontwikkelen van efficiëntere zoektechnieken. Dit werk draagt ook op een meer directe manier bij aan het verbeteren van de efficiëntie van algoritmes door nieuwe methodes te beschrijven waarmee algoritmes beter gebruik kunnen maken van de structuur van een probleem en de zoekruimte.
Michel Medema voerde zijn onderzoek uit bij het Bernoulli Institute for Mathematics, Computer Science and Artificial Intelligence, afdeling Distributed Systems. Hij vervolgt zijn loopbaan als postdoc bij de Rijksuniversiteit Groningen.