Seminário de Combinatória UFF

O Seminário de Combinatória continua as suas atividades de forma online. Agradecemos a oportunidade de receber o professor e pesquisador Guilherme Fonseca (Aix-Marseille Université).

Emitiremos certificados de participação para Atividade Complementar. Basta colocar seu nome completo, instituição de origem, e e-mail no Chat ao final do seminário.

Não é necessária inscrição prévia. 

Agradecemos a presença e a ajuda na divulgação. Compartilhem!

Cadastre-se na lista de emails para atualizações sobre os próximos seminários ou eventuais mudanças. 

Data: 18/04/2022 (segunda-feira)

Horário: 15h

Sala: meet.google.com/fpb-tzsk-ram

Palestrante:  Guilherme Fonseca (Aix-Marseille Université)

Título: Abordagem da equipe Shadoks para partição mínima em subgrafos de plano

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.

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

****** 

title: Shadoks team Approach to Minimum Partition into Plane Subgraphs

abstract: We explain the heuristics used by the Shadoks team to win first place in the CG:SHOP 2022 challenge that considers the minimum partition into plane subgraphs. The goal is to partition a set of segments into as few subsets as possible such that segments in the same subset do not cross each other. The challenge has given 225 instances containing between 2500 and 75000 segments. For every instance, our solution was the best among all 32 participating teams.

Observation: This is a joint work with Crombez e Gerard (Université Clermont Auvergne), e Gonzalez-Lorenzo (Université Aix-Marseille).

Nossos seminários acontecem regularmente desde 2015 e todas as ações podem ser encontradas em:

http://www.antenabrasil.uff.br/index.php/pt-br/acoes/seminario-combinatoria