Algoritmos de aproximação para problemas de Corte em Grafos

• Processo: 19/24866-3
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de janeiro de 2020
• Data de Término da vigência: 31 de dezembro de 2020
• Á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: Esther Calderan Hoffmann
• 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): Algoritmos de aproximação Otimização combinatória Programação linear inteira Grafos Análise de algoritmos
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | Problemas de Corte em Grafos | programação linear inteira | Otimização Combinatória

Resumo

Nos problemas de corte em grafos busca-se encontrar um conjunto de arestas que, ao serem removidas, desconectam determinados vértices, cumprindo requisitos e particularidades dos mais diversos cenários. Esses problemas são bastante relevantes tanto do ponto de vista de dificuldade teórica, muito deles sendo problemas NP-difíceis para os quais diversos algoritmos de aproximação são conhecidos, quanto pela motivação de aplicações práticas por modelarem problemas de computação distribuída, identificação de vulnerabilidades em redes e agrupamento de dados.Este projeto tem como objetivos o estudo de algoritmos de aproximação para problemas de corte em grafos, como o Multiway Cut e o Multicut, a implementação e testes de alguns destes algoritmos, além da produção de um relatório técnico com os principais resultados estudados.Esta iniciação científica também visa introduzir a candidata à área de pesquisa científica e objetiva complementar sua formação na área de Ciência da Computação, aprofundando seu conhecimento em otimização combinatória, algoritmos de aproximação e técnicas de projeto e análise de algoritmos. (AU)