algoritmer
13. december 2021
Som den første dansker modtager professor Mikkel Thorup den prestigefulde Fulkerson Prize
Algoritmer
Fulkerson-prisen går til de mest berømte forskningsresultater inden for diskret matematik, som er den gren af matematikken, der er mest relevant for datalogi og datavidenskab. Professor Mikkel Thorup tildeles som den første dansker nogensinde prisen for at finde løsningen på et problem, som det tog ham 18 år at regne ud.
Det kræver både tid, vedholdenhed og tålmodighed at løse den slags matematiske problemer, som algoritmikken beskæftiger sig med – og gerne luftforandring undervejs.
- Det er som en bjergvandring i et ukendt terræn. Man har måske en ide om en mulig vej til en bestemt top, men så viser vejen sig at være afskåret af nogle dybe kløfter. Mens man er derude, må man hele tiden være kreativ og søge nye veje. Man skal også være fleksibel, for ofte opdager man andre toppe, som det bestemt er værd at besøge, fortæller professor Mikkel Thorup.
Problemet, han har løst, handler om kantsammenhængen i netværk, der er et af grafteoriens mest fundamentale problemer. Det går ud på at finde ud af, hvor mange kanter du kan fjerne fra et netværk, før det går i stykker.
Efter 15 år i USA, en flytning tilbage Danmark og endelig en tur til Japan, hvor Mikkel Thorup besøgte sin japanske medforfatter, professor Ken-Ichi Kawarabayashi, og gik utallige ture rundt om kejserpaladset i Tokyo, kom det store gennembrud:
En effektiv algoritme, der finder kantsammenhængen i et netværk helt uden brug af tilfældighed; altså en algoritme, der kan stå hundrede procent inde for sine svar. Resultatet blev udgivet i en videnskabelig artikel i 2018 i Journal of the ACM.
- I de 15 år jeg var ledende industriforsker ved AT&T Laboratories, lå løsningen på dette problem altid højest på min ønskeliste. Netværk finder vi alle mulige steder, for eksempel i form af vejnetværk og sociale medier. Når man har et stort netværk, vil man gerne have en effektiv algoritme, der hurtigt kan finde ud af kantsammenhængen; altså hvor tæt netværket er på at gå i stykker, forklarer Mikkel Thorup.
Langvarig indflydelse på feltet
Der er blevet forsket i problemet om kantsammenhæng siden 1961. Mikkel Thorup blev selv først rigtigt interesseret i problemet, da han i 1997 var gæsteforsker ved Massachusetts Institute of Technology (MIT).
En berømt professor fra MIT, David Karger, havde i 1996 fremlagt en effektiv løsning på problemet, men hans gennembrud var en randomiseret algoritme, der anvender tilfældighed. Det betyder, at man aldrig kan være hundrede procent sikker på, om Kargers algoritme giver det rigtige svar.
Selvom Kargers algoritme siger, at netværket hænger fint sammen, kan det være lige ved at falde fra hinanden. Kargers store uløste problem var at finde en effektiv algoritme, der ikke brugte tilfældighed, og hvor man derfor kan stole hundrede procent på svaret.
American Mathematical Society (AMS), der er verdens største matematiksamfund og står for at uddele Fulkerson-prisen sammen med the Mathematical Optimization Society (MOS), skriver om Mikkel Thorups og Ken-Ichi Kawarabayashis løsning:
- Deres arbejde forbedrer ikke blot algoritmens køretid, hvor imponerende det end er. [...] Artiklen introducerer flere betydningsfulde nye ideer, som vil få langvarig indflydelse på feltet.
Læs den fulde begrundelse fra AMS her.
Mikkel Thorup og Ken-Ichi Kawarabayashis teoretiske gennembrud har været med til at inspirere den videre forskning på området, og artiklen var i december 2021 allerede blevet citeret 87 gange.
Forstå problemet om kantsammenhæng
Problemet handler om, hvor godt netværk hænger sammen. I et netværk har vi nogle knuder og nogle kanter, der forbinder dem. Disse netværk (også kaldet grafer) optræder mange steder. Det kan være som vejnetværk, hvor kanterne er veje, og knuderne er kryds. Det kan også være som sociale netværk, for eksempel Facebook, hvor knuderne er mennesker med kanter til deres venner.
Når man har sådan et netværk, kan man spørge, hvor mange kanter man skal fjerne, for at det går i stykker. Det kaldes kantsammenhængen. Den blå graf nedenfor har kantsammenhæng 2, for den går i stykker, hvis vi fjerner de to kanter, der krydser den røde streg.
Om Fulkerson-prisen
Fulkerson-prisen er opkaldt efter pioneren Delbert Ray Fulkerson (1924-1976), som var den ene ophavsmand til Ford-Fulkerson-algoritmen, en af de mest kendte algoritmer til at løse strømningsproblemer i netværk.
Prisen er siden 1979 blevet uddelt hvert tredje år til de mest betydningsfulde videnskabelige artikler inden for diskret matematik, herunder algoritmik og grafteori, der befinder sig i krydsfeltet mellem matematik og datalogi. Tidligere års priser er både gået til rene matematiske artikler og mere datalogiske artikler.
Inden for datalogi er prisen blevet uddelt for berømte resultater som Leonid Khachiyans polynomielle algoritme til lineær programmering fra 1979 og til Manindra Agrawals, Neeraj Kayals og Nitin Saxenas resultat om ”PRIMES is in P” fra 2006.
Blandt de kendte matematikresultater finder man Kenneth Appels og Wolfgang Hakens artikel om firfarvesætningen fra 1977 samt Thomas Hales’ artikel om Keplers formodning fra 2005.
Om Mikkel Thorup
Mikkel Thorup er en af verdens førende eksperter inden for algoritmik og datastrukturer. Han er oprindelig uddannet civilingeniør fra Danmarks Tekniske Universitet og har en ph.d. fra Oxford University.
Fra 1998 til 2013 arbejdede han som ledende industriforsker hos den verdenskendte amerikanske tele- og forskningsgigant AT&T Bell Labs, der ejer en stor del af internettet og udlejer virtuelle netværk til store virksomheder som IBM og General Motors. Her opnåede han 18 patenter, udgav mere end 100 videnskabelige artikler og fik den højest mulige udmærkelse som Fellow of AT&T.
Siden 2013 har Mikkel Thorup været professor på Datalogisk Institut på Københavns Universitet. Han er i dag leder for forskningssektionen Algorithms and Complexity samt leder af BARC-centret (Basic Algorithms Research Copenhagen). Centrets forskere har gang på gang har gjort matematiske gennembrud, som har resulteret i, at Københavns Universitet ifølge CSRankings lå på fjerdepladsen i 2021 over de bedste universiteter i verden målt på antal topartikler indenfor algoritmik.
Mikkel Thorup modtog i 2015 Danmarks største individuelle forskerpris, Villum Kann Rasmussens Årslegat til Teknisk og Naturvidenskabelig Forskning på fem millioner kroner. Mikkel Thorup har desuden modtaget adskillige andre prestigefyldte priser, bl.a. MAA Robbins Prize inden for matematik og Fellow of ACM inden for datalogi. Udover Fulkerson-prisen har han for nylig også modtaget en 20-Year STOC Test of Time Award.
Kontakt
Mikkel Thorup
Professor, Datalogisk Institut
Sektionsleder for Algorithms and Complexity og centerleder for BARC
mthorup@di.ku.dk
Caroline Wistoft
Kommunikationskonsulent, Datalogisk Institut
cawi@di.ku.dk