BARC is off to a flying start with 10 accepted papers for SODA'18
No less than 10 papers authored or co-authored by members of BARC at DIKU have made it to the top algorithms event of the year, the ACM-SIAM Symposium on Discrete Algorithm (SODA’18) in New Orleans.
As a newly founded research center for basic algorithms, BARC already climbs to a significant position by representing this number of papers at SODA. Additionally, head of BARC, Professor Mikkel Thorup, is Invited Plenary Speaker at the conference.
The research behind the 10 SODA accepts has been funded by an Advanced Grant from the Danish Council for Independent Research by the Marie Curie Fellowship program, and, of course, by DIKU.
- These 10 papers means that our newly started BARC center is off to a flying start, says Mikkel Thorup.
Discovery eliminates severe bottleneck for Google and Vimeo
BARC is dedicated to fundamental research of algorithms theory but the people behind it have a track record of astonishing algorithmic discoveries leading to major industrial applications.
One of those discoveries is described in the article Consistent hashing with bounded loads and is among the SODA accepts. This discovery eliminates a severe bottleneck for companies like Google and Vimeo, serving hundreds of millions of users every day and has revolutionized load balancing and allowed scaling up to today’s data traffic worldwide.
It is a general article about a theoretical discovery but has had substantial impact on the industry already by addressing assigning clients to servers in a dynamic environment where both clients and servers can leave the system. This result has since been discussed in industrial blogs such as Google’s research Blog and Vimeo’s Engineering Blog.
The 10 accepted papers
- The Entropy of Backwards Analysis
Mathias Bæk Tejs Knudsen and Mikkel Thorup - Dynamic Bridge-Finding in Õ(log² n) Amortized Time
Jacob Holm, Eva Rotenberg and Mikkel Thorup - Consistent Hashing with Bounded Loads
Vahab Mirrokni, Mikkel Thorup and Morteza Zadimoghaddam - A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time
Stephen Alstrup, Agelos Georgakopoulos, Eva Rotenberg and Carsten Thomassen - Online bipartite matching with amortized O(log2 n) replacements
Aaron Bernstein, Jacob Holm and Eva Rotenberg - The Bane of Low-Dimensionality Clustering
Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg and Alan Roytman - Better Tradeoffs for Exact Distance Oracle in Planar Graphs
Paweł Gawrychowski, Shay Mozes, Oren Weimann and Christian Wulff-Nilsen - Hierarchical Clustering: Objective Functions and Algorithms
Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn and Claire Mathieu - A Fast Approximation Scheme for Low-Dimensional k-Means
Vincent Cohen-Addad - A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals
Vincent Cohen-Addad, Éric Colin de Verdière and Arnaud de Mesmay
To read the full version of the paper Consistent Hashing with Bounded Loads by Vahab Mirrokni, Mikkel Thorup and Morteza Zadimoghaddam, go to https://arxiv.org/abs/1608.01350