Desarrollo de Indicadores de Casos Aplicables a la Selección de Algoritmos en el Problema 2-Partition
2009; National Polytechnic Institute; Volume: 13; Issue: 1 Linguagem: Inglês
10.13053/cys-13-1-1226
ISSN2007-9737
Autores Tópico(s)Optimization and Packing Problems
ResumoIN 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 TRANSFOR-MATION 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 AL-GORITHMS THAT BETTER SOLVES AN INSTANCE OF THE 2-PARTITION PROBLEM. IN THIS THESIS A NEW APPROACH OF SOLUTION IS PRO-POSED 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
Referência(s)