Семинар лаборатории ЛАТАС
Тема: Эффективные алгоритмы подсчета числа целых точек в многогранниках и их приложения.
Докладчик: Дмитрий Грибанов (лаборатория ЛАТАС, НИУ ВШЭ — Нижний Новгород)
Доклад является продолжением двух прошлогодних докладов на аналогичную тему. На нем мы, наконец, полностью разберем и проанализируем новый алгоритм подсчета количества целых точек в многогранниках. Дополнительно, я приведу некоторые новые приложения этого алгоритма к задачам из области комбинаторной оптимизации и целочисленного программирования. Например, к задаче целочисленного программирования с разреженной матрицей ограничений и к задачам о максимальном независимом мультимножестве и о минимальном вершинном мультипокрытии.
English
Title: Effective algorithms for integer points counting in polyhedra and its applications.
Speaker: Dmitry Gribanov (LATNA laboratory, HSE NN)
Abstract: This talk is a continuation of my two last year reports on a similar topic. On it, we will finally finish the analysis of a new integer points counting algorithm. Additionally, I will give some new applications of this algorithm to problems from the field of combinatorial optimization and integer programming. For example, to ILP problems with sparse matrices, and for the maximum independent multiset and minimum vertex multicover problems.
Язык семинара: English
Приглашаются все желающие.
Явка аспирантов школы компьютерных наук обязательна.
