Uma heurística gulosa para o problema de classificação geodésica

Abstract

This work proposes a greedy heuristic with the goal of generating a good feasible solution for the Geodesic Classification (GC) problem. This problem was introduced in (ARAÚJO et al., 2019), where the authors also presented an integer linear programming model to solve it. The GC problem consists to classify new data, according to pre-established data represented by a graph of similarities. To do so, we must identify patterns defined by geodesic convexity. In this work, we deal with the multi-groups version of the GC problem in order to identify geodesic convexity patterns on graphs with better accuracy. We analyze the performance of the proposed heuristic using computational experiments considering realistic and random instances.