Algoritmos de aproximacao para problemas de classificacao metrica.

• Processo: 01/12166-3
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de março de 2002
• Data de Término da vigência: 29 de fevereiro de 2004
• Á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: Evandro Cesar Bracht
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Algoritmos de aproximação Otimização combinatória
• Palavra(s)-Chave do Pesquisador: Algoritmos De Aproximacao | Otimizacao Combinatoria

Resumo

Neste projeto estamos interessados em investigar o Problema de Classificação Métrica (PCM) (Metric Labeling Problem) sob a abordagem de algoritmos de aproximação. Este problema foi introduzido há poucos anos sob a abordagem de aproximação. É um problema que generaliza problemas bem conhecidos na literatura. Neste problema estamos interessados em classificar um dado conjunto de objetos em atributos. Dentre as atribuições possíveis, desejamos aquela que minimiza certos custos, definidos através de uma métrica. Algoritmos de aproximação é uma das áreas que tem recebido grande atenção dos pesquisadores de otimização e teoria da computação nos últimos anos. Isto se deve às novas técnicas que têm surgido, de caráter mais genérico, no desenvolvimento de algoritmos para problemas de otimização. Nesta abordagem estamos interessados tanto em resultados teóricos como resultados práticos. Nosso objetivo é estudar o problema de classificação métrica focando principalmente nas versões onde há grande interesse prático. Iremos implementar os algoritmos mais promissores e iremos comparar os resultados dos algoritmos de aproximação implementados através de algoritmos exatos ou através de delimitantes obtidos para soluções ótimas. (AU)

Publicações acadêmicas

(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)

BRACHT, Evandro Cesar. Algoritmos de aproximação para o problema de classificação metrica. 2004. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.