Prijswinnaar 2014: Dr. Bart Jansen

Informatie- en communicatietechnologie

dr. B.M.P. Jansen (Nijmegen, 5 augustus 1986) voor zijn dissertatie “The Power of Data Reduction, Kernels for Fundamental Graph Problems”, verdedigd op 1 juli 2013 aan de Universiteit van Utrecht.

Dr. Bart Jansen (1986), juli 2013 te Utrecht gepromoveerd op het proefschrijft ‘The Power of Data Reduction, Kernels of Fundamental Graph Problems’

Bart Jansen was ten tijde van de uitreiking werkzaam als postdoctoraal onderzoeker bij de ‘Algorithms Research Group’ van het departement Informatica van de Universiteit van Bergen, Noorwegen.

Toelichting van de jury over zijn dissertatie:

Het fundamentele onderzoek van dr. Bart Jansen beweegt zich op het snijvlak van twee wetenschappelijke disciplines. Dat zijn de theoretische informatica en de discrete wiskunde. Het geeft een belangrijke impuls aan een sterk in opkomst zijnde stroming binnen de complexiteitstheorie, namelijk geparameterizeerde complexiteit. Deze stroming behelst een ‘positivistische’ toenadering op zekere computerberekeningsproblemen die, in termen van de klassieke complexiteitstheorie, vaak geen algoritmische oplossing ofwel computerprogramma toelaten dat efficiënt uitgevoerd kan worden op alle concrete invullingen van zo’n probleem.

Dit positivisme wordt gevoed door het volgende fenomeen. Door de problemen in kwestie via een speciale ‘lens’ te bezien, laten deze soms een oplossing toe die substantieel is dan op basis van de probleemgrootte, d.w.z., de data-omvang van concrete probleeminvullingen, zou mogen worden. De hiertoe is invoering van een extra ‘dimensie’, een parameter, die een zeker structureel, wiskundig aspect van het probleem als zodanig isoleert en kwantificeert.

Een wel geïnformeerde keuze kan dan een algemene oplossing mogelijk maken waarbij dit aspect nagenoeg complexiteit opeist. Dat heet kernelization. Door de bijbehorende parameter vervolgens geschikt te onderdrukken ten opzichte van de probleemgrootte, kan er een trade-off ontstaan waarbij de resulterende van het probleem veel beheersbaar is dan de meest algemene, formulering daarvan.

Dat praktische relevantie hieronder niet hoeft te lijden is gelegen in het feit dat in het wild voorkomende problemeninvullingen meer dan eens een natuurlijke neiging vertonen tot specialisatie: het zijn dan waarschijnlijk ‘worst-case’ manifestaties in hun algemene probleemklasse. Daarmee worden ze mogelijk vatbaar voor ‘snelle behandeling’ onder dit paradigma. Met andere woorden, geparametrizeerde complexiteit heeft een aanzienlijk praktisch potentieel.

Het werk van Jansen heeft de geparameterizeerde complexiteit verrijkt met twee nieuwe fundamentele gereedschappen. Cross-composition is een techniek waarmee de mogelijkheden en begrenzingen van efficiënte kernelization veel beter en ruimer dan voorheen bestudeerd kunnen worden. Het is bovendien gebaseerd op een krachtig samenspel van de klassieke complexiteitstheorie en de geparameterizeerde verfijning daarvan; zo zijn klassiek en modern weer met elkaar vervlochten.

Zijn programmatische aanpak van parameter ecology maakt het mogelijk dat meer structurele eigenschappen van een probleem dan voorheen benut kunnen worden. Vervolgens past hij deze nieuwe gereedschappen succesvol toe op belangrijke structurele problemen uit de grafen-theorie, d.w.z., de wiskunde van netwerken van verbindingen. Dat is een terrein met enorme relevantie bij toepassingen van de wiskundige informatica, bij voorbeeld optimalizatie, scheduling zoals het spoorboekje van de NS, floorplanning bij chip-design, Google page-rank, handelsreizigersproblematiek en nog veel meer.