Семинар МЛ АТиП «Задача подсчета количества целых точек в k-модулярных симплексах и близких полиэдрах»
Международная лаборатория алгебраической топологии и её приложений факультета компьютерных наук продолжает цикл семинаров. Приглашаем подключиться к трансляции в этот четверг в 18:10.
Идентификатор конференции: 857 9926 6425
Пароль необходимо запросить у менеджера лаборатории
Контакты: Анастасия Камышанова (akamyshanova@hse.ru)
«Задача подсчета количества целых точек в k-модулярных симплексах и близких полиэдрах»
Докладчик - Дмитрий Грибанов, младший научный сотрудник лаборатории алгоритмов и технологий анализа сетевых структур факультета информатики, математики и компьютерных наук НИУ ВШЭ.
Аннотация. Рассмотрим симплекс, заданный системой вида A x <= b, где A и b - есть целочисленные матрица и вектор. Симплекс называется k-модулярным если абсолютная величина ранговых миноров матрицы A ограничена числом k. На докладе будет показано, что задача подсчета целых точек внутри k-модулярных симплексов разрешима за полиномиальное время, если фиксировать k. Также в докладе будут рассмотрены возможные обобщения этого факта и различные частные случаи, допускающие более эффективные алгоритмы решения.