BARC får en flyvende start med 10 accepterede artikler ved SODA'18 – Københavns Universitet

Videresend til en ven Resize Print Bookmark and Share

Datalogisk Institut, DIKU > Nyheder > DIKU-nyheder 2017 > SODA'18

02. november 2017

BARC får en flyvende start med 10 accepterede artikler ved SODA'18

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