Семинар МЛ АТиП «Задача подсчета количества целых точек в k-модулярных симплексах и близких полиэдрах»

Международная лаборатория алгебраической топологии и её приложений факультета компьютерных наук продолжает цикл семинаров. Приглашаем подключиться к трансляции в этот четверг в 18:10.

Идентификатор конференции: 857 9926 6425

Пароль необходимо запросить у менеджера лаборатории

Контакты: Анастасия Камышанова (akamyshanova@hse.ru)

«Задача подсчета количества целых точек в k-модулярных симплексах и близких полиэдрах»

Докладчик - Дмитрий Грибанов, младший научный сотрудник лаборатории алгоритмов и технологий анализа сетевых структур факультета информатики, математики и компьютерных наук НИУ ВШЭ.

Аннотация. Рассмотрим симплекс, заданный системой вида A x <= b, где A и b - есть целочисленные матрица и вектор. Симплекс называется k-модулярным если абсолютная величина ранговых миноров матрицы A ограничена числом k. На докладе будет показано, что задача подсчета целых точек внутри k-модулярных симплексов разрешима за полиномиальное время, если фиксировать k. Также в докладе будут рассмотрены возможные обобщения этого факта и различные частные случаи, допускающие более эффективные алгоритмы решения.