Loading...
Please wait, while we are loading the content...
Similar Documents
Algoritmos de aproximação para o problema de classificação metrica
| Content Provider | Semantic Scholar |
|---|---|
| Author | Bracht, Evandro C. Miyazawa, Flávio Keidi |
| Copyright Year | 2004 |
| Abstract | Em um problema de classificacao 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 classificacao seja consistente com alguns dados que temos sobre o problema. Este trabalho apresenta um estudo do problema de classificacao metrica atraves de algoritmos aproximados. Os algoritmos aproximados conhecidos para este problema sao baseados na solucao de grandes programas lineares e sao impraticaveis para instâncias de tamanho moderado e grande. Apresentamos um algoritmo 8 log n-aproximado, analisado pela tecnica primal-dual, que apesar de possuir fator de aproximacao maior que os algoritmos anteriores, pode ser aplicado a grandes instâncias. Mostramos tambem que este fator de aproximacao e 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 resolucao de programas lineares. Para estas instâncias o algoritmo proposto apresentou solucoes de boa qualidade com um ganho consideravel no tempo computacional Abstract |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://repositorio.unicamp.br/jspui/bitstream/REPOSIP/276375/1/Bracht_EvandroCesar_M.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |