Please use this identifier to cite or link to this item: http://bibdigital.epn.edu.ec/handle/15000/23028
Title: Programación Semidefinida para la solución del Problema de Particionamiento de Grafos K-Way Balanceado con Restricciones de Peso.
Authors: Flores Bravo, Santiago Román
Keywords: RESTRICCIÓN DE PESO
BALANCEADO
EXPERIMENTACIÓN COMPUTACIONAL
GRAFOS
Issue Date: Sep-2022
Publisher: Quito : EPN, 2022.
Citation: 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.
Abstract: 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.
Description: 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
Appears in Collections:TIC- Ingeniería Matemática

Files in This Item:
File Description SizeFormat 
CD 12441.pdf504,6 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.