1. Repositorio Institucional del Tecnológico Nacional de México (RI - TecNM)
2. Tesis de Posgrado
3. Tamaulipas
4. Instituto Tecnológico de Ciudad Madero
5. Tesis
6. Tesis de Maestría
7. Maestría en Ciencias de la Computación

Título :	Estrategias de búsqueda local para el problema de SUMCUT
Autor :	Zamarron Escobar, Daniel Enrique.
Fecha de publicación :	2013-06-01
Editorial :	Tecnológico Nacional de México
metadata.dc.publisher.tecnm:	Instituto Tecnológico de Ciudad Madero
Descripción :	En este trabajo de investigaci´on se aborda el problema de dise˜nar estrategias eficientes de b´usqueda local para el problema del SUMCUT. El SUMCUT es un problema NP-duro que consiste en minimizar la suma de los cortes de un grafo conexo; dicho problema tiene aplicaciones en la gen´etica, en la arqueolog´ıa y en la reducci´on de matrices dispersas. La contribuci´on m´as importante de este tra bajo consiste en cinco nuevas estrategias de b´usqueda local, la cuales incorporan mecanismos eficientes para la predicci´on del costo de una inserci´on consecutiva los cuales reducen la complejidad de las b´usquedas locales de O(n 3 ) a O(n 2 ). Para validar la eficiencia de las estrategias propuestas se desarroll´o una soluci´on metaheur´ıstica del problema SUMCUT, basada en una b´usqueda local iterada con procesamiento celular. Se realizaron pruebas experimentales con instancias est´andar, los cuales mostraron que para las instancias m´as grandes que las b´usque das locales propuestas, reducen el tiempo de ejecuci´on del algoritmo al menos un 90 % alcanzando el mismo nivel de calidad. Resultados parciales de este trabajo se incorporaron en el art´ıculo “Estrategias de b´usqueda local para el problema de SUMCUT”, el cual fue publicado en el VI Encuentro de Investigadores de Posgrado en el ´area de Ciencias Computacionales realizado en el Instituto Tecnol´ogico de Ciudad Madero los d´ıas del 10 al 14 de diciembre del 2012.
metadata.dc.type:	info:eu-repo/semantics/masterThesis
Aparece en las colecciones:	Maestría en Ciencias de la Computación

Este ítem está protegido por copyright original Visualizar la licencia

Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons