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

Titre:	Estrategias de búsqueda local para el problema de SUMCUT
Auteur(s):	Zamarron Escobar, Daniel Enrique.
Date de publication:	2013-06-01
Editeur:	Tecnológico Nacional de México
metadata.dc.publisher.tecnm:	Instituto Tecnológico de Ciudad Madero
Description:	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
Collection(s) :	Maestría en Ciencias de la Computación

Ce document est protégé par copyright Voir la licence

Ce document est autorisé sous une licence de type Licence Creative Commons