Por favor, use este identificador para citar o enlazar este ítem:
http://bibdigital.epn.edu.ec/handle/15000/23028
Título: | Programación Semidefinida para la solución del Problema de Particionamiento de Grafos K-Way Balanceado con Restricciones de Peso. |
Autor: | Flores Bravo, Santiago Román |
Palabras clave: | RESTRICCIÓN DE PESO BALANCEADO EXPERIMENTACIÓN COMPUTACIONAL GRAFOS |
Fecha de publicación: | sep-2022 |
Editorial: | Quito : EPN, 2022. |
Citación: | Flores Bravo, S.R.(2022). Programación Semidefinida para la solución del Problema de Particionamiento de Grafos K-Way Balanceado con Restricciones de Peso. 30 páginas. Quito : EPN. |
Resumen: | Semidefinite Programming is useful for solving different convex optimization problems; in this work we use it to find a solution to the weight-constrained balanced k-way graph partitioning problem. Two formulations for the problem are developed, one of them iterative, based on a linear relaxation of the semi-definite formulation built for the problem. Several instances are simulated for computational experimentation, the results of the implementation are presented, as well as conclusions and recommendations. |
Descripción: | La Programación Semidefinida es útil para resolver distintos problemas de optimización convexa; en este trabajo la empleamos para encontrar una solución al problema de particionamiento de grafos k-way balanceado con restricciones de peso. Se desarrolla dos formulaciones del problema propuesto, una de ellas iterativa, basadas en emplear una relajación lineal a la formulación semidefinida construida para el problema. Se simula varias instancias para la experimentación computacional, se presentan los resultados de la implementación y finalmente se presentan conclusiones y recomendaciones |
URI: | http://bibdigital.epn.edu.ec/handle/15000/23028 |
Tipo: | bachelorThesis |
Aparece en las colecciones: | TIC - Ingeniería Matemática |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
CD 12441.pdf | 504,6 kB | Adobe PDF | Visualizar/Abrir |
Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.