А вот крутая новость. Когда-то давно, в начале нулевых, люди начали смотреть на сетевые алгоритмы с позиций конкурентного анализа (это то, чем я давно занимаюсь вместе с Кириллом Коганом). И для первой самой простой модели, shared memory switch, была сразу, ещё в 2001, доказана для конкурентности верхняя оценка 2 и нижняя оценка sqrt(2) на тот самый алгоритм и общая 4/3 на любой алгоритм.
И вот почти 20 лет никто не мог эти оценки сдвинуть; многие пытались, верхнюю даже немножко сдвинули (правда, асимптотически она там всё равно к двум шла, но снизу), а нижнюю нет. И вот теперь это получилось, в основном благодаря новому взгляду на оптимальный алгоритм, который позволяет доказывать нижние оценки не только руками, но и полуавтоматически.
Всё это заслуга двух студентов СПбГУ — Ивана Бочкова и [id25011914|Никиты Гаевого] — и несравненного Лёши Давыдова; сам я, как водится, скорее примазался. Статью подали, на arxiv выложили, все ужасно крутые, и всем огромное спасибо!
https://arxiv.org/abs/1907.04399
И вот почти 20 лет никто не мог эти оценки сдвинуть; многие пытались, верхнюю даже немножко сдвинули (правда, асимптотически она там всё равно к двум шла, но снизу), а нижнюю нет. И вот теперь это получилось, в основном благодаря новому взгляду на оптимальный алгоритм, который позволяет доказывать нижние оценки не только руками, но и полуавтоматически.
Всё это заслуга двух студентов СПбГУ — Ивана Бочкова и [id25011914|Никиты Гаевого] — и несравненного Лёши Давыдова; сам я, как водится, скорее примазался. Статью подали, на arxiv выложили, все ужасно крутые, и всем огромное спасибо!
https://arxiv.org/abs/1907.04399
Here's the cool news. Once upon a time, at the beginning of the 2000s, people began to look at network algorithms from the standpoint of competitive analysis (this is what I have been doing for a long time with Kirill Kogan). And for the first simplest model, the shared memory switch, it was immediately, back in 2001, proven for competitiveness, the upper estimate is 2 and the lower estimate sqrt (2) for the same algorithm and the total 4/3 for any algorithm.
And for almost 20 years no one could move these estimates; many tried, the top one was even shifted a little (though asymptotically it still went to two there, but from the bottom), but the bottom one did not. And now this has happened, mainly thanks to a new look at the optimal algorithm, which allows one to prove lower bounds not only by hand, but also semi-automatically.
All this is the merit of two students from St. Petersburg State University - Ivan Bochkov and [id25011914 | Nikita Gayevy] - and the incomparable Lyosha Davydov; I myself, as usual, rather cling to it. The article was submitted, posted on arxiv, everyone is awfully cool, and many thanks to everyone!
https://arxiv.org/abs/1907.04399
And for almost 20 years no one could move these estimates; many tried, the top one was even shifted a little (though asymptotically it still went to two there, but from the bottom), but the bottom one did not. And now this has happened, mainly thanks to a new look at the optimal algorithm, which allows one to prove lower bounds not only by hand, but also semi-automatically.
All this is the merit of two students from St. Petersburg State University - Ivan Bochkov and [id25011914 | Nikita Gayevy] - and the incomparable Lyosha Davydov; I myself, as usual, rather cling to it. The article was submitted, posted on arxiv, everyone is awfully cool, and many thanks to everyone!
https://arxiv.org/abs/1907.04399
У записи 46 лайков,
4 репостов,
1294 просмотров.
4 репостов,
1294 просмотров.
Эту запись оставил(а) на своей стене Сергей Николенко
