Жадные алгоритмы в задачах о покрытии и раскраске" А.М. Райгородский (Яндекс)_день1 _часть1

В наших лекциях мы расскажем о двух классических проблемах. Первая из них состоит в отыскании хроматического числа графа, т.е. минимального количества цветов, в которые можно так покрасить вершины графа, чтобы вершины, соединенные ребром, были разного цвета. Вторая проблема сводится к нахождению наименьшего вершинного покрытия для ребер гиперграфа, т.е. такого множества вершин минимальной мощности, которое имеет непустое пересечение с каждым ребром гиперграфа. Обе проблемы алгоритмически трудны. Основной наш пафос в том, что в некотором смысле простые жадные алгоритмы дают "почти" точные результаты. Однако мы докажем и много других интересных фактов.

Видео Жадные алгоритмы в задачах о покрытии и раскраске" А.М. Райгородский (Яндекс)_день1 _часть1 канала Университетское ТВ УрФУ