Polynomial-Time Evaluation of Aardal-Lenstra Denumerants via Constant Term Method
Aardal and Lenstra systematically studied hard knapsack problems of the form $a_1x_1+\cdots+a_nx_n=b$, where $a_i=p_iM+r_iN$, $(M,N)$ is a coprime pair of positive integers, and the integers $|p_i|, |r_i|$ are small relative to $M$ and $N$. We investigate the corresponding challenging denumerant problem (i.e., counting the number of nonnegative integer solutions) and present a polynomial-time algorithm. This eliminates the computational bottlenecks caused by large values of $M$, $N$ and $b$. The proposed algorithm achieves a time complexity of $O(n^4Δ^2\log n\logΔ)$, which depends solely on…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.11477
curl -X POST /api/v1/records/arxiv/2607.11477/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.11477/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'