Defesa de Mestrado

              Algoritmos de Aproximação para o 
             Problema de Classificação  Métrica


                    Evandro C. Bracht

              Sexta-feira, 4 de junho de 2004

            Auditório do IC (IC1), 10:00hs <---- Notem o horário


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 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. 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.