BIBDIGITAL
El Repositorio Digital Institucional de la Escuela Politécnica Nacional, ofrece acceso abierto al texto completo de la producción científica de los miembros de la comunidad politécnica. El objetivo del Repositorio, es constituirse como el registro permanente de consulta académica, maximizando su visibilidad, accesibilidad e impacto.
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 |
| Type: | bachelorThesis |
| Appears in Collections: | TIC - Ingeniería Matemática |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| CD 12441.pdf | 504,6 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.