Сибирские электронные математические известия
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Сиб. электрон. матем. изв.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Сибирские электронные математические известия, 2022, том 19, выпуск 2, страницы 613–626
DOI: https://doi.org/10.33048/semi.2022.19.051
(Mi semr1525)
 

Дискретная математика и математическая кибернетика

A faster algorithm for counting the integer points number in $\Delta$-modular polyhedra

D. Gribanova, D. Malyshevba

a National Research University Higher School of Economics, 25/12, Bolshaja Pecherskaja str., Nizhny Novgorod, 603155, Russia
b Lobachevsky State University of Nizhny Novgorod, 23, Gagarina ave., Nizhny Novgorod, 603950, Russia
Список литературы:
Аннотация: Let a polytope $\mathcal{P}$ be defined by a system $A x \leq b$. We consider the problem to count a number of integer points inside $\mathcal{P}$, assuming that $\mathcal{P}$ is $\Delta$-modular. The polytope $\mathcal{P}$ is $\Delta$-modular if all the rank sub-determinants of $A$ are bounded by $\Delta$ in the absolute value.
We present a new FPT-algorithm, parameterized by $\Delta$ and by the number of simple cones in the normal fun triangulation of $\mathcal{P}$, which is more efficient for $\Delta$-modular problems, than the approach of A. Barvinok et al. [1, 2, 3, 4, 5]. To this end, we do not directly compute the short rational generating function for $\mathcal{P} \cap \mathbb{Z}^n$, which is commonly used for the considered problem. We compute its particular representation in the form of exponential series that depends on one variable, using the dynamic programming principle. We completely do not use the A. Barvinok's unimodular sign decomposition technique.
Using our new complexity bound, we consider different special cases that may be of independent interest. For example, we give FPT-algorithms for counting the integer points number in $\Delta$-modular simplicies and similar polytopes that have $n + O(1)$ facets. For any fixed $m$, we give an FPT-algorithm to count solutions of the unbounded $m$-dimensional $\Delta$-modular knapsack problem. For the case, when $\Delta$ grows slowly with respect to $n$, we give a counting algorithm, which is more effective, than the state of the art ILP feasibility algorithm due to [6, 7].
Ключевые слова: integer linear programming, short rational generating function, bounded sub-determinants, multidimensional knapsack problem, subset-sum problem, counting problem.
Финансовая поддержка Номер гранта
Российский научный фонд 21-11-00194
The article was prepared under financial support of Russian Science Foundation grant No 21-11-00194.
Поступила 25 апреля 2022 г., опубликована 31 августа 2022 г.
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.165
MSC: 52C07
Язык публикации: английский
Образец цитирования: D. Gribanov, D. Malyshev, “A faster algorithm for counting the integer points number in $\Delta$-modular polyhedra”, Сиб. электрон. матем. изв., 19:2 (2022), 613–626
Цитирование в формате AMSBIB
\RBibitem{GriMal22}
\by D.~Gribanov, D.~Malyshev
\paper A faster algorithm for counting the integer points number in $\Delta$-modular polyhedra
\jour Сиб. электрон. матем. изв.
\yr 2022
\vol 19
\issue 2
\pages 613--626
\mathnet{http://mi.mathnet.ru/semr1525}
\crossref{https://doi.org/10.33048/semi.2022.19.051}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4478152}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/semr1525
  • https://www.mathnet.ru/rus/semr/v19/i2/p613
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024