Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 46 min ago
PreprintarXiv licencearXiv

A polynomial time algorithm for almost bounded denumerant

  • Guoce Xin
  • Chen Zhang
  • Zihao Zhang
Open at sourcePDFDOICite

Abstract

Sylvester's denumerant d(t; A) counts the number of nonnegative integer solutions to ∑i=1N ai xi = t, where A = (a1, …, aN) is a sequence of positive integers with gcd(A) = 1. In 2025, Xin and Zhang gave a polynomial time algorithm in N for computing d(t; A) when the entries of A are bounded by a constant. In this paper, we extend this algorithm by incorporating Barvinok's algorithm, enabling it to handle the case where a fixed number of entries of A are allowed to be unbounded.

Related

  1. A Polynomial-Time Algorithm for the Minimal Input/Output Node Cardinality Disturbance Decoupling Problem via Output Feedback
    Luca Claude Gino Lebon, Jorke de Vlas, Johannes K. Fichte +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  2. A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs
    Zhiqiang Xu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input
    Zhao Song, Lichen Zhang
    arXivPreprintCC BY-NC-ND 4.0Full textAnalysis & PDEsOptimisation & controlarXiv
  4. A tight 1/3-approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem
    Fabio Ciccarelli, Fabio Furini
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  5. Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm
    Sailesh Kamalahasan, Raghav Paladugu, Archana Khurana
    arXivPreprintCC BY-NC-ND 4.0Full textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{xin2026polynomial,
  title = {{A polynomial time algorithm for almost bounded denumerant}},
  author = {Guoce Xin and Chen Zhang and Zihao Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2608.14985},
  eprint = {2608.14985},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.14985},
}
RIS
TY  - UNPB
TI  - A polynomial time algorithm for almost bounded denumerant
AU  - Guoce Xin
AU  - Chen Zhang
AU  - Zihao Zhang
PY  - 2026
DA  - 2026/10/16
PB  - arXiv
DO  - 10.48550/arxiv.2608.14985
UR  - https://arxiv.org/abs/2608.14985
AB  - Sylvester's denumerant d(t; A) counts the number of nonnegative integer solutions to ∑_i=1^N a_i x_i = t, where A = (a_1, …, a_N) is a sequence of positive integers with gcd(A) = 1. In 2025, Xin and Zhang gave a polynomial time algorithm in N for computing d(t; A) when the entries of A are bounded by a constant. In this paper, we extend this algorithm by incorporating Barvinok's algorithm, enabling it to handle the case where a fixed number of entries of A are allowed to be unbounded.
ER  -