Multilevel + Neural Network Heuristic for the Graph Bisection Problem on Geometrically Connected Graphs

dc.creatorHernandez, G.
dc.creatorBravo, F.
dc.creatorMontealegre, P.
dc.creatorNuñez, F.
dc.creatorSalinas, L.
dc.date2010
dc.date2010
dc.date2023-05-10T16:51:11Z
dc.date.accessioned2023-07-15T10:26:15Z
dc.date.available2023-07-15T10:26:15Z
dc.identifierhttp://sedici.unlp.edu.ar/handle/10915/152730
dc.identifierhttp://39jaiio.sadio.org.ar/sites/default/files/39jaiio-hpc-07.pdf
dc.identifierissn:1851-9326
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/7491861
dc.descriptionThe Multilevel algorithm (ML) has been applied successfully as a metaheuristic for different combinatorial optimization problems: Graph Partitioning, Traveling Salesman, Graph Coloring, see refs. [6,7,18]. The main difficulty of ML are the convergence times needed to obtain solutions at a distance of 7% - 5% to the best known solution in large scale problems. In order to reduce these convergence times we studied numerically a Parallel Multilevel heuristic with Neural Network partitioning and uncoarsening + refinement phases (PML+PNN) for the Graph Bisection Problem on geometrically connected graphs. Our main result establish that for graphs with n∊[4000,12000] vertices, the performance of the parallel ML+NN heuristic increases linearly as n increases with respect to the parallel ML heuristic. For n∊{10000,12000} the distance to the best solution found is 0.32,0.25 respectively that is obtained with a quadratic computing time. This suggests improving the performance of the PML+PNN heuristic by means of a hill climbing improvement heuristic.
dc.descriptionSociedad Argentina de Informática e Investigación Operativa
dc.formatapplication/pdf
dc.format3249-3257
dc.languageen
dc.rightshttp://creativecommons.org/licenses/by-nc-sa/4.0/
dc.rightsCreative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
dc.subjectCiencias Informáticas
dc.subjectGraph Bisection Problem
dc.subjectMultilevel + Neural Network Heuristic
dc.titleMultilevel + Neural Network Heuristic for the Graph Bisection Problem on Geometrically Connected Graphs
dc.typeObjeto de conferencia
dc.typeObjeto de conferencia


Este ítem pertenece a la siguiente institución