Repositorio de producción científica de la Universidad de Sevilla

An application of integer programming to the decomposition of numerical semigroups

 

Advanced Search
 
Opened Access An application of integer programming to the decomposition of numerical semigroups
Cites

Show item statistics
Icon
Export to
Author: Blanco Izquierdo, Víctor
Puerto Albandoz, Justo
Department: Universidad de Sevilla. Departamento de Estadística e Investigación Operativa
Date: 2012
Published in: SIAM Journal on Discrete Mathematics, 26(3), 1210-1237
Document type: Article
Abstract: This paper addresses the problem of decomposing a numerical semigroup into mirreducible 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.
Cite: Blanco Izquierdo, V. y Puerto Albandoz, J. (2012). An application of integer programming to the decomposition of numerical semigroups. SIAM Journal on Discrete Mathematics, 26 (3), 1210-1237.
Size: 312.4Kb
Format: PDF

URI: http://hdl.handle.net/11441/36532

DOI: 10.1137/110821809

This work is under a Creative Commons License: 
Attribution-NonCommercial-NoDerivatives 4.0 Internacional

This item appears in the following Collection(s)