Desarrollo de Indicadores de Casos Aplicables a la Selección de Algoritmos en el Problema 2-Partition



Título del documento: Desarrollo de Indicadores de Casos Aplicables a la Selección de Algoritmos en el Problema 2-Partition
Revista: Computación y sistemas
Base de datos: PERIÓDICA
Número de sistema: 000328700
ISSN: 1405-5546
Autors: 1
1
1
Institucions: 1Centro Nacional de Investigación y Desarrollo Tecnológico, Cuernavaca, Morelos. México
Any:
Període: Jul-Sep
Volum: 13
Número: 1
Paginació: 111-119
País: México
Idioma: Español
Tipo de documento: Artículo
Enfoque: Experimental
Resumen en español En este trabajo se abordó el problema de transformar instancias e indicadores de complejidad entre los problemas Bin-Packing y 2-Partition. Diversos investigadores han realizado reducciones y transformaciones polinomiales entre problemas NP-completos, los principales son Garey & Johnson, Karp y Cook. La transformación de 2-Partition a Bin-Packing existe en la literatura. Sin embargo no existe la transformación de Bin-Packing a 2-Partition, ni la transformación de indicadores con el fin de ser usados en la selección de algoritmos que mejor resuelven una instancia del problema 2-Partition. En esta tesis se propone un nuevo enfoque de solución para transformar instancias, desarrollar indicadores de complejidad y solución de los problemas Bin-Packing al problema 2-Partition, mediante una metodología y el desarrollo de lenguajes formales para expresar las instancias de ambos problemas
Resumen en inglés In this work we approach the problem of transforming instances and complexity indicators between the problems discovered being Bin-Packing and 2-Partition. Several researchers have reductions and polynomial transformations between NP-complete problems, the main ones Garey & Johnson, Karp and Cook. The transformation of 2-Partition into Bin-Packing exists in literature. Nevertheless, does not exist the transformation of Bin-Packing into 2-Partition, nor the transformation of indicators with the purpose of to be used in the selection of algorithms that better solves an instance of the 2-Partition problem. In this thesis a new approach of solution is proposed to transform instances, to develop complexity indicators and to solve the Bin-Packing problem to the 2-Partition problem, by means of a methodology and formal languages to express the instances of both problems
Disciplines Ciencias de la computación,
Matemáticas
Paraules clau: Matemáticas aplicadas,
Transformación polinomial,
Lenguajes formales,
Compiladores,
NP-Completo,
Algoritmos
Keyword: Computer science,
Mathematics,
Applied mathematics,
Polynomial transformation,
Formal languages of instances,
Compilers,
NP-Complete,
Algorithms
Text complet: Texto completo (Ver HTML)