Estudo teórico de algoritmos aproximativos para uma classe de problemas de grafos

• Processo: 96/11643-2
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de abril de 1997
• Data de Término da vigência: 30 de abril de 1997
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cláudio Leonardo Lucchesi
• Beneficiário: Christiane Neme Campos
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Algoritmos de aproximação Solução de problemas
• Palavra(s)-Chave do Pesquisador: Algoritmos Aproximativos

Resumo

Estudo teórico de algoritmos aproximativos salientado a mudança de enfoque observada, nos últimos anos, no projeto dos mesmos. Nota-se que a elaboração destes algoritmos, inicialmente ad hoc, tem sido vista de uma forma mais genérica visando englobar uma gama maior de problemas. O cerne do projeto é o trabalho de D.P. Williamson onde foi desenvolvido um método primal-dual para algoritmos aproximativos que se encaixa em vários problemas conhecidos. Um trabalho de impacto, pois conseguiu encontrar soluções aproximadas para estes problemas utilizando o mesmo método padrão. Finalizando serão estudadas outras ferramentas para projetos de algoritmos aproximativos (métodos métrico, aleatório e semi-definido). (AU)