Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/276375
Full metadata record
DC FieldValueLanguage
dc.contributor.CRUESPUNIVERSIDADE ESTADUAL DE CAMPINASpt_BR
dc.identifier(Broch.)pt_BR
dc.descriptionOrientador: Flavio Keidi Miyazawapt_BR
dc.descriptionDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computaçãopt_BR
dc.format.mimetypeapplication/octet-streampt_BR
dc.languagePortuguêspt_BR
dc.typeDISSERTAÇÃOpt_BR
dc.titleAlgoritmos de aproximação para o problema de classificação metricapt_BR
dc.contributor.authorBracht, Evandro Cesar, 1977-pt_BR
dc.contributor.advisorMiyazawa, Flávio Keidi, 1970-pt_BR
dc.contributor.institutionUniversidade Estadual de Campinas. Instituto de Computaçãopt_BR
dc.subjectTeoria da computaçãopt_BR
dc.subjectOtimização combinatóriapt_BR
dc.subject.otherlanguageComputer theoryen
dc.subject.otherlanguageCombinatorial optimizationen
dc.description.abstractResumo: 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 computacionalpt
dc.description.abstractAbstract: 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 timeen
dc.publisher[s.n.]pt_BR
dc.date.issued2004pt_BR
dc.identifier.citationBRACHT, Evandro Cesar. Algoritmos de aproximação para o problema de classificação metrica. 2004. Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/276375>. Acesso em: 4 ago. 2018.pt_BR
dc.description.degreelevelMestradopt_BR
dc.description.degreedisciplineCiência da Computaçãopt_BR
dc.description.degreenameMestre em Ciência da Computaçãopt_BR
dc.contributor.committeepersonalnameLee, Orlandopt_BR
dc.contributor.committeepersonalnameFernandes, Cristina Gomespt_BR
dc.date.defense2004-04-06T00:00:00Zpt_BR
dc.date.available2018-08-04T11:49:51Z-
dc.date.accessioned2018-08-04T11:49:51Z-
dc.description.provenanceMade available in DSpace on 2018-08-04T11:49:51Z (GMT). No. of bitstreams: 1 Bracht_EvandroCesar_M.pdf: 694440 bytes, checksum: b7f0c4ac260849f98329f238c91ec2bd (MD5) Previous issue date: 2004en
dc.identifier.urihttp://repositorio.unicamp.br/jspui/handle/REPOSIP/276375-
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Bracht_EvandroCesar_M.pdf678.16 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.