Título: The Geodesic Classification Problem on Graphs

Data: 12/08/2019

Horário: 09:00h

Local: Sala de Videoconferência da STI

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 multidimensional space. We name such a problem the Geodesic Classification Problem (GC) 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 properties for the single-group case are carried over to the multi-group case. We relate or findings with results from the literature concerning Euclidean classification. Finally, we run computational experiments in order to evaluate the computational efficiency and the classification accuracy of the proposed approaches by comparing them with some classic resolution methods for the Euclidean convexity classification problem.

Banca:

• Prof. Dr. Manoel Campelo (MDCC/UFC - Orientador)
• Prof. Dr. Ricardo Cordeiro Correa (UFRRJ - Coorientador)
• Prof. Dr. Rafael Andrade (MDCC/UFC)
• Prof. Dr. Yoshiko Wakabayashi (IME/USP)
• Prof. Dr. Martine Labbé (Université Libre de Bruxelles)