| Что: | Лекция |
| Когда: | Суббота, 23 апреля 2011, 19:15–20:50 |
| Где: | ПОМИ РАН |
Задача о вершинно-взвешенном мультиразрезе, описание политопа. Двойственная линейная программа, T-пути и мультипотоки. Полуцелочисленность, 2-приближенный алгоритм и оракул отделения. Задача о кратчайшем ветвлении, описание верхней оболочки политопа. Прямо-двойственный алгоритм поиска кратчайшего ветвления.
https://books.google.ru/books?id=EILqAmzKgYIC&lpg=PP1&pg=PA121#v=onepage&q&f=false (Section 14.3)
