Fast Algorithms via Convex Relaxation
2 068
49.2
Microsoft Research333 тыс
Следующее
09.03.18 – 3 20247:32Популярные
19.10.23 – 4 7223:36
27.10.22 – 82844:44Опубликовано 9 марта 2018, 19:32
In Theoretical CS many of the fastest algorithms are obtained by considering the Linear Programming (LP) relaxation of the problem. In this talk, I will survey several results on the effectiveness of employing the more general *convex* relaxation. We discovered that for a host of classical problems, their convex relaxation is often a more natural starting point to design fast algorithms. Examples include submodular minimization, market equilibrium computation and approximate Caratheodory. Our journey will involve some fun interplay of convex optimization with tools from discrete optimization and economics.
See more at microsoft.com/en-us/research/v...
See more at microsoft.com/en-us/research/v...
Свежие видео
1 день – 2 7315:10
2 дня – 1901:18
8 дней – 5930:19
9 дней – 6670:26
15 дней – 8 0640:52Случайные видео
12 дней – 84 13112:26
258 дней – 8780:44
309 дней – 10 6111:19
336 дней – 5 08816:03
13.06.23 – 6 7710:55
20.05.23 – 3 5410:29
23 часа – 2 5250:58
1 день – 3 2590:28
9 дней – 5 3185:59
10 дней – 2 290 6656:58
16 дней – 14 3391:00
17 дней – 322 3263:55
20 дней – 12 5490:21
1 день – 33 14011:47