| Journal: | Computación y sistemas |
| Database: | PERIÓDICA |
| System number: | 000328700 |
| ISSN: | 1405-5546 |
| Authors: | Ruiz-Vanoye, Jorge A1 Pérez Ortega, Joaquín1 Pazos Rangel, Rodolfo A1 |
| Institutions: | 1Centro Nacional de Investigación y Desarrollo Tecnológico, Cuernavaca, Morelos. México |
| Year: | 2009 |
| Season: | Jul-Sep |
| Volumen: | 13 |
| Number: | 1 |
| Pages: | 111-119 |
| Country: | México |
| Language: | Español |
| Document type: | Artículo |
| Approach: | Experimental |
| Spanish abstract | 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 |
| English abstract | 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 |
| Keyword: | 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 |
| Full text: | Texto completo (Ver HTML) |
