### A greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual techniqueA greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual technique

Access Restriction
Subscribed

 Author Bracht, Evandro C. ♦ Meira, Luis A A ♦ Miyazawa, F. K. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2005 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Approximation algorithms ♦ Graph labeling Abstract We consider the uniform metric labeling problem. This NP-hard problem considers how to assign objects to labels respecting assignment and separation costs. The known approximation algorithms are based on solutions of large linear programs and are impractical for moderate- and large-size instances. We present an 8log $\textit{n}-approximation$ algorithm that can be applied to large-size instances. The algorithm is greedy and is analyzed by a primal-dual technique. We implemented the presented algorithm and two known approximation algorithms and compared them at randomized instances. The gain of time was considerable with small error ratios. We also show that the analysis is tight, up to a constant factor. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2005-12-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 10

#### Open content in new tab

Source: ACM Digital Library