voltarData: 18/04/2022
Título: Abordagem da equipe Shadoks para partição mínima em subgrafos de plano.
Palestrante: Guilherme Fonseca, Aix-Marseille Université.
Data: 18 de Abril de 2022, 15 h.
Sala: Google Meet.
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.
Obs: Este é um trabalho em conjunto com Crombez e Gerard (Université Clermont Auvergne), e Gonzalez-Lorenzo (Aix-Marseille Université).
Veja: Vídeo Apresentação