Algoritmos de aproximação para problemas de empacotamento e conjunto independente

• Processo: 23/13972-2
• Modalidade de apoio: Bolsas no Brasil - Iniciação Científica
• Data de Início da vigência: 01 de dezembro de 2023
• Data de Término da vigência: 30 de novembro de 2024
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Flávio Keidi Miyazawa
• Beneficiário: Gabriel Medrano Silva
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Vinculado ao auxílio: 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos, AP.TEM
• Assunto(s): Algoritmos de aproximação Otimização combinatória Problemas de corte e empacotamento
• Palavra(s)-Chave do Pesquisador: Algoritmos de Aproximação | Conjunto independente | Otimização Combinatória | Problemas de Empacotamento | Departamento de Teoria da Computação - DTC

Resumo

Problemas de otimização combinatória são alvos de muito estudo devido ao grande número de aplicações práticas. Dentre as maneiras de tratar esse tipo de problema, algoritmos de aproximação são uma das principais ferramentas, devido a sua rapidez em comparação com outras abordagens. Esse projeto aborda as principais técnicas desse paradigma, focando em dois problemas clássicos que possuem vasta literatura, o problema de empacotamento geométrico, e o problema de conjunto independente de formas geométricas.