Metric Rounding of LP Relaxations
729
16.2
Microsoft Research334 тыс
Следующее
12.08.16 – 2 3361:28Популярные
02.11.23 – 3231:07
02.11.23 – 1 8231:44Опубликовано 12 августа 2016, 4:03
LP relaxations interpreted as metrics (or distance functions in graphs) are useful in designing approximation algorithms for cut problems. This was illustrated by designing an exact algorithm for minimum s-t cut, a 2-approximation for multiway cut in graphs, a 2-approximation for the multicut problem in trees and finally a logarithmic approximation for the multicut problem in general graphs.
Свежие видео
2 дня – 175 6651:00
5 дней – 1 7130:32
5 дней – 3830:47
6 дней – 7070:16
6 дней – 482 7660:57Случайные видео
281 день – 107 0413:28
322 дня – 6 5760:29
21.07.23 – 8 3100:58
27.12.22 – 17 3130:24
06.12.22 – 657 45711:34
14.04.21 – 7 4884:29
6 дней – 31 55610:32
7 дней – 44216:35
11 дней – 2 5620:59
13 дней – 1 2002:11
14 дней – 1 4240:21
17 дней – 22 8441:00
17 дней – 526 4360:49