2024/06/20 by Guoce Xin, Xin, Guoce, Yingrui Zhang +3
Business, Management and Accounting · Engineering · Mathematics · #05--08 #Combinatorics (math.CO) #Consumer Market Behavior and Pricing #FOS: Mathematics #Mathematics and Applications #Primary 52C07 #Secondary 05--04 #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2406.13974
openalex publication_date 2024/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we focus on knapsack cones, a specific type of simplicial cones that arise naturally in the context of the knapsack problem x1 a1 + ⋯ + xn an = a0. We present a novel combinatorial decomposition for these cones, named DecDenu, which aligns with Barvinok's unimodular cone decomposition within the broader framework of Algebraic Combinatorics. Computer experiments support us to conjecture that our DecDenu algorithm is polynomial when the number of variables n is fixed. If true, DecDenu will provide the first alternative polynomial algorithm for Barvinok's unimodular cone decomposition, at least for denumerant cones. The CTEuclid algorithm is designed for MacMahon's partition analysis, and is notable for being the first algorithm to solve the counting problem for Magic squares of order 6. We have enhanced the CTEuclid algorithm by incorporating DecDenu, resulting in the LLLCTEuclid algorithm. This enhanced algorithm makes significant use of LLL's algorithm and stands out as an effective elimination-based approach.