Assistant Professor at the Algorithms Logic and Graphs section at DTU Compute Eva Rotenberg together with co-authors receives Best Paper Award at the ACM-SIAM Symposium on Discrete Algorithms (SODA'18)
SODA is an annual, academic conference in the field of theoretical computer science. It is considered one of the top conferences for research in algorithms and complexity and this year no less than six articles from DTU Compute have been accepted at the prestigious conference. Four of those, including the award-winning article, are co-authored by Eva Rotenberg.
New technique, long-standing problem
The main criteria for accepting papers and especially for giving the Best Paper Award at SODA are the introduction of an interesting and innovative technique or problem, or a solution to a long-term theoretical problem.
Describing the awarded paper, Eva Rotenberg, elaborates:
“Sometimes, we need to invent new algorithms for solving a problem efficiently. Other times, we take an existing algorithm and prove that it has interesting properties. In my opinion, what makes an algorithm useful is the guarantee that it works well, and that is exactly what we have provided in our article.”
The simplest algorithm works
The long-standing problem of Online Bipartite Matching with Replacements has applications in data storage, hashing, web hosting, and streaming content delivery.
All of these situations have in common that clients need to be assigned to a “server” immediately as they arrive, but they may later need to be reassigned to accommodate new clients.
“We looked at ways to minimize the “switching cost”; the cost of reassigning clients, and we focused on the simplest imaginable greedy algorithm: When a new client arrives, choose the rearrangement that makes as few changes as possible”, explains Eva Rotenberg.
Using a novel technique of describing the necessity of the servers as independent of the assignment, the group managed to prove that using this algorithm, the average client will experience significantly fewer changes than was previously known possible. The result is not only an exponential improvement over previous work, but also exemplifies how complicated approaches sometimes have little or no advantage over the simplest possible.
The research is joint work with Jacob Holm (University of Copenhagen) and Aaron Bernstein (TU Berlin) and the award will be presented to the authors at the SODA Conference 7 – 10 January 2018 in New Orleans.
Read the scientific article here