2015/10/07 by Marcel Moralès, Marcel Morales, Morales, Marcel +2
Computer Science · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #Commutative Algebra (math.AC) #Commutative Algebra and Its Applications #FOS: Mathematics #Polynomial and algebraic computation #math.AC #math.CO
paper · pdf · doi:10.48550/arxiv.1510.01973
openalex publication_date 2015/10/07 · arxiv created 2015/12/18 · arxiv updated 2015/12/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let consider n natural numbers a_1 ,… , a_n . Let S be the numerical semigroup generated by a_1 ,… , a_n . Set A=K[ta_1, … , ta_n]=K[x_1, … , x_n]/I. The aim of this paper is: \beginenumerate\item Give an effective pseudo-polynomial algorithm on a_1, which computes The Apéry set and the Frobenius number of S. As a consequence it also solves in pseudo-polynomial time the integer knapsack problem : given a natural integer b, b belongs to S?\item The \gbb of I for the reverse lexicographic order to x_n,… ,x_1, without using Buchberger's algorithm. \item \iniI for the reverse lexicographic order to x_n,… ,x_1.\item A as a K[t a_1 ]-module. \endenumerate We dont know the complexity of our algorithm. We need to solve the "multiplicative" integer knapsack problem: Find all positive integer solutions (k_1, … , k_n) of the inequality ∏_i=2n (k_i+1)≤ a_1+1. This algorithm is easily implemented. The implementation of this algorithm "frobenius-number-mm", for n=17 , can be downloaded in \hfill\breakhttps://www-fourier.ujf-grenoble.fr/~morales/frobenius-number-mm