Christian Wulff-Nilsen modtager Best Paper Award – Københavns Universitet

Videresend til en ven Resize Print Bookmark and Share

Datalogisk Institut, DIKU > Nyheder > DIKU-nyheder 2015 > Christian Wulff-Nilsen...

20. november 2015

Christian Wulff-Nilsen modtager Best Paper Award

Best paper award

Den 10. oktober 2015 fik Christian Wulff-Nilsen, algoritmeforsker ved Datalogisk Institut, Københavns Universitet (DIKU), en god nyhed. Hans artikel med titlen ”Near-Optimal Light Spanners” er forud for SODA 2016, som er hovedkonferencen inden for algoritmik, blevet tildelt en Best Paper Award. Prisen uddeles af SIAM - Society for Industrial and Applied Mathematics.

Sammen med Shiri Chechik fra Tel-Aviv University har Christian Wulff-Nilsen beskrevet en algoritme til at konstruere en delgraf af en given graf, så delgrafen har lavest mulig samlet kantvægt og samtidig approksimativt bevarer alle korteste vej-afstande. En sådan delgraf kaldes en light spanner. Den nye konstruktion giver et essentielt optimalt tradeoff mellem vægten af spanneren og approksimationsfaktoren for korteste vej-afstande. Et tilsvarende resultat er tidligere kun kendt for spannere, der minimerer antallet af kanter i stedet for den samlede kantvægt.

I praksis kan opdagelsen bruges til at effektivisere en lang række områder, fx reducere omkostningerne i et kommunikationsnetværk hvor man ønsker at kunne sende beskeder med så lille forsinkelse som muligt mellem de enkelte knudepunkter i netværket. Her kan konstruktionen af en light spanner benyttes.

-Det er fedt at få denne anerkendelse fra hovedkonferencen inden for algoritmik, og så har det været sjovt at arbejde sammen med Shiri på artiklen, fortæller Christian.

Det vigtigste kriterium for at komme i betragtning til en Best Paper Award er, at artiklen skal bidrage til enten indførelsen af en stærk ny teknik, løsning af et mangeårigt åbent problem eller introduktion og løsning af et interessant og vigtigt nyt problem.

SIAM’s Best Paper Award uddeles ved SODA 2016 konferencen, der afholdes i Arlington, Virginia, USA d. 10.-12. januar 2016, hvor både Shiri og Christian deltager. Artiklen forventes at blive offentliggjort online på konferencesitet i slutningen af december 2015.