Algoritmos de aproximação para o problema de classificação metrica

AUTOR(ES)

Evandro Cesar Bracht

DATA DE PUBLICAÇÃO

2004

RESUMO

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

ASSUNTO(S)

teoria da computação combinatorial optimization computer theory otimização combinatoria

Documentos Relacionados

• Algoritmos paralelos para o problema da mochila.
• Algoritmos genéticos para o problema de Docking proteína-ligante
• Analise de algoritmos para o problema de minimização sem restrições
• Algoritmos aproximados para solucionar o problema de Bin Packing unidimensional.
• Uma estratégia híbrida para o problema de classificação multirrótulo