Data: 01/06/2022, às 16:00 horas (GMT-3, horário de Brasília).
Título: Abordagem da equipe Shadoks para partição mínima em subgrafos de plano
Palestrante: Guilherme Fonseca (Aix-Marseille Université)

Resumo: Explicamos as heurísticas usadas pela equipe Shadoks para conquistar o primeiro lugar no desafio CG:SHOP 2022 que considera a partição mínima em subgrafos planos. O objetivo é particionar um conjunto de segmentos no menor número possível de subconjuntos, de modo que os segmentos do mesmo subconjunto não se cruzem. O desafio deu 225 instâncias contendo entre 2.500 e 75.000 segmentos. Para cada instância, nossa solução foi a melhor entre todas as 32 equipes participantes.

Este é um trabalho em conjunto com Crombez e Gerard (Université Clermont Auvergne), e Gonzalez-Lorenzo (Aix-Marseille Université).