The geodesic classification problem on graphs

Detalhes bibliográficos
Ano de defesa: 2019
Autor(a) principal: Araújo, Paulo Henrique Macêdo de
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: eng
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://www.repositorio.ufc.br/handle/riufc/45051
Resumo: We define and study a discrete version of the classical classification problem in the Euclidean space. The problem is defined on a graph, where the unclassified vertices have to be classified taking into account the given classification of other vertices. The vertex partition into classes is grounded on the concept of geodesic convexity on graphs, as a replacement for the Euclidean convexity in the multidimensional space. We name such a problem the Geodesic Classification (GC) problem and consider two variants: 2-class single-group and 2-class multi-group. We propose integer programming based approaches for each considered version of the GC problem along with branch-and-cut algorithms to solve them exactly. We also carry out a polyhedral study of the associated polyhedra, which includes some families of facet-defining inequalities and separation algorithms. Facetness conditions for the single-group case are carried over to the multi-group case. We relate our findings with results from the literature concerning Euclidean classification. Finally, we run computational experiments to evaluate the computational efficiency and the classification accuracy of the proposed approaches by comparing them with some classic solution methods for the Euclidean convexity classification problem.