Сайт использует сервис веб-аналитики Яндекс Метрика с помощью технологии «cookie». Пользуясь сайтом, вы даете согласие на использование данной технологии.
0:00:00 Задача о вершинном покрытии 0:06:00 Формулировка для ЦЛП 0:11:00 Линейная релаксация 0:14:00 Случай невзвешенных графов 0:23:30 Округление переменных решения 0:29:00 Сравнение с OPT 0:31:30 Комб. алг. для невзвешенного покрытия 0:40:30 Проблема для взвешенного случая 0:42:15 Сложение неравенств для взвешенного случая 0:46:30 Предположение ограничения на веса 0:50:57 Пафосный момент 0:54:50 Комб. алг. для взвешенного случая 1:01:30 Оценка для суммы игреков 1:05:50 Оценка для OPT Дата лекции: 24.02.2022 Лектор: Дайняк Александр Борисович Съёмка: Денис Швейкин Монтаж: Артём Фартыгин
