Metraipolis › archive › dc_d9da89f175bf
A Simple Algorithm for Counting Solutions to Integer Programs — arXiv:2610.19200
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.19200
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-15T14:37:58.026Z
- SHA-256 of the archived text
8bc6202a29a08c35fcaf7cc7c3a439fbdd3f8c1c49eede6cd9645e07c0cda9a2- Stable URL of this page
https://metraipolis.com/documento/dc_d9da89f175bf
How to cite
A Simple Algorithm for Counting Solutions to Integer Programs — arXiv:2610.19200 — arXiv (en), https://arxiv.org/abs/2610.19200 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d9da89f175bf (Metraipolis archive dc_d9da89f175bf, sha256 8bc6202a29a08c35fcaf7cc7c3a439fbdd3f8c1c49eede6cd9645e07c0cda9a2)
BibTeX
@misc{dcd9da89f175bf,
title = {A Simple Algorithm for Counting Solutions to Integer Programs — arXiv:2610.19200},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.19200},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d9da89f175bf; sha256 8bc6202a29a08c35fcaf7cc7c3a439fbdd3f8c1c49eede6cd9645e07c0cda9a2},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.19200. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We consider the problem of counting solutions to integer linear programming problems of the form $\{x \in \mathbb{Z}^n_{\geq 0} : Ax = b\}$ where $A \in \{-\Delta,\ldots,\Delta\}^{m \times n}$ and $b \in \mathbb{Z}^m$. We present an algorithm that counts solutions with $(n\Delta)^{m + o(1)}\! \cdot \log\lVert b\rVert$ arithmetic operations. This simplifies the algorithm of Gribanov and Malyshev, who considered the problem for the more general setting in which $A$ is $\Delta$-modular.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.19200 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T13:59:54.793Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).