Bra algoritmer for vanskelige problemer

En algoritme er ganske enkelt en liste med instruksjoner for hvordan man løser en oppgave. For at algoritmen skal være bra, må den tilfredsstille to krav: for det første må den som følger algoritmen løse oppgaven på en tilfredsstillende måte; og for det andre må den som følger algoritmen bli ferdig med oppgaven innen rimelig tid og ressursbruk.

Avhandlingen utforsker hvorvidt vi kan lage bra algoritmer for en håndfull av vanskelige problemer beskrevet som spørsmål om matematiske grafer. En matematisk graf er tett knyttet til det vi i virkeligheten kjenner som nettverk, men kan også brukes til å modellere andre situasjoner innenfor et vidt spekter av fagområder.

Mange interessante problemer på grafer er såkalt NP-komplette, hvilket innebærer at eksistensen av en skikkelig bra algoritme for problemet automatisk vil gi bra algoritmer for tusenvis av andre vel-studerte problemer. Det er derfor vanlig å anta at NP-komplette problemer ikke kan løses med en bra algoritme.

Ved å utnytte strukturer i grafen, er det likevel mulig å skape gode algoritmer for mange slike problemer; at grafen er strukturert på en eller annen måte er ofte tilfelle i praksis, avhengig avhengig av hvilket nettverk eller situasjon som modelleres. I fagfeltet parameterisert kompleksitet finnes det verktøy for å analysere slike strukturer matematisk, og vi kan undersøke samspillet mellom ulike parametere og hvordan de påvirker tid og ressursbruk.

I Torstein sin avhandling gir han parameteriserte algoritmer for en rekke NP-komplette graf-problemer, men beviser også at en del andre slike algoritmer ikke kan eksistere under standard antagelser innen kompleksitetsteori.

Avhandlingen er tilgjengelig her: https://bora.uib.no/handle/1956/22108

Personalia

Torstein J. F. Strømme har vært doktorgradsstudent i algoritmegruppen ved Institutt for Informatikk siden september 2015, under veiledning av professor Fedor V. Fomin. Han fullførte sin mastergrad (2015) ved Universitetet i Bergen, bachelorgrad (2013) ved Carnegie Mellon University, og tok fagbrev i elektronikk (2008) som del av TAF-programmet ved Knarvik vidaregåande skule.