Algoritmos para o Balanced Multiway Cut Problem.

• Processo: 24/13239-6
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de outubro de 2024
• Data de Término da vigência: 30 de setembro de 2025
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Mário César San Felice
• Beneficiário: Maristella Ramalho Rangel
• Instituição Sede: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brasil
• Assunto(s): Meta-heurística Otimização combinatória
• Palavra(s)-Chave do Pesquisador: Cortes em grafos | meta-heurísticas | Otimização Combinatória

Resumo

O Balanced Multiway Cut Problem (BMCP) é uma combinação do Multiway Cut Problem com o Balanced Cut Problem, ambos variações NP-Difíceis do clássico problema do Corte Mínimo. No BMCP, deseja-se encontrar um conjunto de arestas, com custo mínimo, que ao serem removidas, particionam o grafo em diversas componentes, de forma que cada componente possua exatamente um terminal e possua no máximo uma fração dos vértices do grafo, sendo o conjunto de vértices terminais e o valor da fração parte da entrada. Neste projeto pretendemos estudar algoritmos clássicos para os problemas de corte citados, e projetar estratégias para resolver o BMCP. Em particular, pretendemos usar a meta-heurística Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking (BRKGA-MP-IPR).Esta iniciação científica também visa introduzir a candidata à área de otimização combinatória, complementando sua formação em ciência da computação. Os resultados obtidos nessa pesquisa deverão ser compilados em um relatório técnico.