Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/94262
Type: Artigo de periódico
Title: A Greedy Approximation Algorithm For The Uniform Labeling Problem Analyzed By A Primal-dual Technique
Author: Bracht E.C.
Meira L.A.A.
Miyazawa F.K.
Abstract: In this paper we present a new fast approximation algorithm for the Uniform Metric Labeling Problem. This is an important classification problem that occur in many applications which consider the assignment of objects into labels, in a way that is consistent with some observed data that includes the relationship between the objects. The known approximation algorithms are based on solutions of large linear programs and are impractical for moderated and large size instances. We present an 8 log n-approximation algorithm analyzed by a primal-dual technique which, although has factor greater than the previous algorithms, can be applied to large sized instances. We obtained experimental results on computational generated and image processing instances with the new algorithm and two others LP-based approximation algorithms. For these instances our algorithm present a considerable gain of computational time and the error ratio, when possible to compare, was less than 2% from the optimum. © Springer-Verlag 2004.
Editor: 
Rights: fechado
Identifier DOI: 
Address: http://www.scopus.com/inward/record.url?eid=2-s2.0-35048821065&partnerID=40&md5=d5e7d6af18f45c5155ec16faff2801f5
Date Issue: 2004
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
There are no files associated with this item.


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