Algoritmos de aproximação para o problema de classificação metrica
Evandro Cesar Bracht
DISSERTAÇÃO
Português
(Broch.)
T/UNICAMP B724a
Campinas, SP : [s.n.], 2004.
Orientador: Flavio Keidi Miyazawa
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
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... Ver mais
apresenta um... Ver mais
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 Ver menos
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 Ver menos
Abstract: In a traditional classification problem, we have a set of n objects and a set of m labels (or classes). We wish to assign one of m labels (or classes) to each one of n objects, in a way that is
consistent with some observed data that we have about the problem. In this work we present... Ver mais
consistent with some observed data that we have about the problem. In this work we present... Ver mais
Abstract: In a traditional classification problem, we have a set of n objects and a set of m labels (or classes). We wish to assign one of m labels (or classes) to each one of n objects, in a way that is
consistent with some observed data that we have about the problem. In this work we present a
study of approximation algorithms for the metric labeling problem. The known approximation
algorithms for this problem are based on solutions of large linear programs and are impractical
for moderate and large size instances. We present an 8 log n-approximation algorithm analyzed
by a primal-dual technique which, although has a factor greater than the previous algorithms,
can be applied to large sized instances. We also show that the analysis is tight, up to a constant
factor. We obtained experimental results on computational generated and image processing instances with the new algorithm and two other LP-based approximation algorithms. For these
instances our algorithm presents good quality solutions with a considerable gain of computational
time Ver menos
consistent with some observed data that we have about the problem. In this work we present a
study of approximation algorithms for the metric labeling problem. The known approximation
algorithms for this problem are based on solutions of large linear programs and are impractical
for moderate and large size instances. We present an 8 log n-approximation algorithm analyzed
by a primal-dual technique which, although has a factor greater than the previous algorithms,
can be applied to large sized instances. We also show that the analysis is tight, up to a constant
factor. We obtained experimental results on computational generated and image processing instances with the new algorithm and two other LP-based approximation algorithms. For these
instances our algorithm presents good quality solutions with a considerable gain of computational
time Ver menos
Algoritmos de aproximação para o problema de classificação metrica
Evandro Cesar Bracht
Algoritmos de aproximação para o problema de classificação metrica
Evandro Cesar Bracht
Exemplares
Nº de exemplares: 2
Não existem reservas para esta obra