Det kan være vanskelig å stemme; å velge vinneren likedan.

Hva er de 10 beste byene å besøke i Norge? For å svare på dette spørsmålet kan vi be alle nordmenn om å stemme og gi sin rangering av deres topp 10, og deretter prøve å kombinere alle stemmene i én rangering. Intuitivt bør den endelige rangeringen minimere uenigheten med alle stemmene. Dette problemet, i informatikk, kalles Kemeny Rank Aggregation -problemet. Å finne en optimal løsning på dette problemet er beviselig vanskelig. Dette betyr at det er lite håp om å finne et dataprogram som kan løse dette problemet generelt. Men dette problemet er fortsatt interessant i praksis. Parameterisert kompleksitet er en gren innen informatikk og kompleksitetsteori som tar sikte på å takle slike problemer. I stedet for å lete etter et program som løser problemet generelt, søker parameteriserte algoritmer å gi et program som fungerer i spesielle tilfeller.

I denne avhandlingen fokuserer vi på et abstrakt problem kalt "Completion of an Ordering." Dette problemet er en generalisering av Kemeny Rank Aggregation -problemet. Denne generaliseringen kan også modellere andre problemer; som ensidig kryssingsminimering og gruppering ved bytting. På vei mot å løse problemet, studerer vi dets parameteriserte kompleksitet. Hovedresultatet er en måte å løse det på i noen spesielle tilfeller. Dette impliserer at vi også utvikler en algoritme som kan brukes til å løse Kemeny Rank Aggregation. Deretter utvidet vi denne algoritmen til ikke å gi en løsning, men et mangfoldig sett med løsninger. Tanken er å la brukerne velge løsningen i stedet for å begrense dem til kun ett alternativ. Siste delen av avhandlingen ser på et annet problem, et rekonfigureringsproblem. I et slikt rekonfigureringsproblem er spørsmålet ikke å finne en løsning, men for å få svar på hvorvidt man kan modifisere en konfigurasjon til å bli en gitt annen konfigurasjon ved hjelp av et begrenset utvalg modifikasjonsteknikker.

Personalia

Emmanuel Arrighi kommer fra Frankrike hvor han tok en mastergrad i informatikk ved ENS Cachan. Han begynte først på Universitetet i Bergen for en ni-måneders praksisperiode i løpet av sitt siste år ved ENS Cachan. Han nøt livet i Bergen og Institutt for informatikk, og bestemte seg for å komme tilbake for å ta doktorgradsstudiene der. Forskningen hans handler om parameterisert kompleksitet.