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