An application of integer programming to the decomposition of numerical semigroups
From MaRDI portal
Abstract: This paper addresses the problem of decomposing a numerical semigroup into m-irreducible numerical semigroups. The problem originally stated in algebraic terms is translated, introducing the so called Kunz-coordinates, to resolve a series of several discrete optimization problems. First, we prove that finding a minimal m-irreducible decomposition is equivalent to solve a multiobjective linear integer problem. Then, we restate that problem as the problem of finding all the optimal solutions of a finite number of single objective integer linear problems plus a set covering problem. Finally, we prove that there is a suitable transformation that reduces the original problem to find an optimal solution of a compact integer linear problem. This result ensures a polynomial time algorithm for each given multiplicity m. We have implemented the different algorithms and have performed some computational experiments to show the efficiency of our methodology.
Recommendations
Cited in
(7)- Fibonacci-like growth of numerical semigroups of a given genus.
- An improved algorithm to compute the -primality
- Irreducible numerical semigroups with multiplicity three and four.
- scientific article; zbMATH DE number 1216241 (Why is no real title available?)
- Applications of Integer Semi-Infinite Programing to the Integer Chebyshev Problem
- Counting Numerical Semigroups by Genus and Even Gaps via Kunz-Coordinate Vectors
- The arithmetic extensions of a numerical semigroup
This page was built for publication: An application of integer programming to the decomposition of numerical semigroups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4899057)
