20 November 2015

Christian Wulff-Nielsen receives Best Paper Award

Best paper award

On October 10, 2015, Christian Wulff-Nilsen, algorithm researcher at the Department of Computer Science, University of Copenhagen (DIKU), received good news. His article entitled "Near-Optimal Light Spanners" to be presented at SODA 2016 (link), the main conference within the algorithms, has been assigned a Best Paper Award. The prize is awarded by SIAM - Society for Industrial and Applied Mathematics.

Together with Shiri Chechik from Tel-Aviv University, Christian Wulff-Nilsen has described an algorithm for constructing a subgraph of a given graph, so that the subgraph has the lowest possible total edge weight whilst approximately retaining all shortest path distances. Such a subgraph is called a light spanner. The new construction provides an essentially optimal tradeoff between the weight of the spanner and the approximation factor for the shortest path distances. A similar result has previously only been known for spanners that minimize the number of edges instead of the total edge weight.

In practice, the discovery might be applicable to a variety of areas, such as reducing the cost in a communication network where you want to send messages with as little delay as possible between the individual nodes in the network. Here, the construction of a light spanner can be used.

-It is great to get this recognition from the main conference within algorithms, and it has been great fun to work with Shiri on the article, says Christian.

The main criteria to be considered for a Best Paper Award is that the article should contribute to a strong new technique, solution of a long-standing open problem or introduction and solution of an interesting and important new problem.

The SIAM Best Paper Award is given at the SODA 2016 Conference, held in Arlington, Virginia, USA January 10 to 12 2016 where both Shiri and Christian will be participating. The article is expected to become online on the conference site by the end of December 2015.