Texto completo
| |
| Autor(es): |
Evandro Cesar Bracht
Número total de Autores: 1
|
| Tipo de documento: | Dissertação de Mestrado |
| Imprenta: | Campinas, SP. |
| Instituição: | Universidade Estadual de Campinas (UNICAMP). Instituto de Computação |
| Data de defesa: | 2004-04-06 |
| Membros da banca: |
Flávio Keidi Miyazawa;
Orlando Lee;
Cristina Gomes Fernandes
|
| Orientador: | Flávio Keidi Miyazawa |
| Resumo | |
Em um problema de classificação tradicional temos um conjunto de n objetos e um conjunto de m classes e queremos classificar cada objeto como pertencente a uma classe, de modo que esta classificação seja consistente com alguns dados que temos sobre o problema. Este trabalho apresenta um estudo do problema de classificação métrica através de algoritmos aproximados. Os algoritmos aproximados conhecidos para este problema são baseados na solução de grandes programas lineares e são impraticáveis para instâncias de tamanho moderado e grande. Apresentamos um algoritmo 8 log n-aproximado, analisado pela técnica primal-dual, que apesar de possuir fator de aproximação maior que os algoritmos anteriores, pode ser aplicado a grandes instâncias. Mostramos também que este fator de aproximação é justo, exceto por um fator constante. Obtivemos resultados experimentais usando instâncias geradas computacionalmente e instâncias de processamento de imagens com o novo algoritmo e com outros dois algoritmos baseados na resolução de programas lineares. Para estas instâncias o algoritmo proposto apresentou soluções de boa qualidade com um ganho considerável no tempo computacional (AU) | |
| Processo FAPESP: | 01/12166-3 - Algoritmos de aproximacao para problemas de classificacao metrica. |
| Beneficiário: | Evandro Cesar Bracht |
| Modalidade de apoio: | Bolsas no Brasil - Mestrado |