BARC får en flyvende start med 10 accepterede artikler ved SODA'18
Intet mindre end 10 artikler forfattet eller medforfattet af medlemmer af DIKUs nye forskningscenter Basic Algorithms Research Copenhagen (BARC) er blevet accepteret til årets førende algoritmebegivenhed, ACM-SIAM Symposium on Discrete Algorithm (SODA’18) i New Orleans, USA.
Som et nyetableret forskningscenter for grundlæggende algoritmik positionerer BARC sig allerede bemærkelsesværdigt ved at præsentere så stort et antal artikler ved SODA. Derudover er BARCs centerleder Professor Mikkel Thorup Invited Plenary Speaker ved konferencen.
Forskningen bag de 10 artikler er finansieret af en Topforsker-bevilling fra Det Frie Forskningsråd, et Marie Curie Postdoc Fellowship og naturligvis af DIKU.
- De 10 artikler betyder, at BARC får en flyvende start, siger Mikkel Thorup.
Opdagelse fjerner markant flaskehals for Google og Vimeo
BARC er dedikeret til grundforskning indenfor algoritmik, men de tilknyttede forskere står bag adskillige algoritmiske opdagelser, der har ført til betydningsfulde anvendelser i industrien.
En af disse opdagelser er beskrevet i artiklen Consistent Hashing with Bounded Loads og er blandt de accepterede SODA-artikler. Denne opdagelse fjerner en markant flaskehals for virksomheder som Google og Vimeo, der dagligt betjener hundredevis af millioner brugere, og det har revolutioneret load balancing og dermed muliggjort en tilpasning til den kraftigt voksende datatrafik på verdensplan.
Det er en generel artikel om en teoretisk opdagelse, men den har allerede fået afgørende indflydelse på industrien ved at behandle det at knytte klienter til servere i et dynamisk miljø, hvor både klienter og servere kan forlade systemet. Siden er dette resultat blevet diskuteret på industrielle blogs som Google’s research Blog og Vimeo’s Engineering Blog.
De 10 accepterede artikler
- 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
For at læse hele artiklen Consistent Hashing with Bounded Loads af Vahab Mirrokni, Mikkel Thorup og Morteza Zadimoghaddam, klik på dette link https://arxiv.org/abs/1608.01350