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

DOI10.1145/1064546.1180623zbMath1190.90085OpenAlexW2119402945MaRDI QIDQ3507758

Evandro C. Bracht, Flávio K. Miyazawa, A. A. Meira Luis

Publication date: 20 June 2008

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1064546.1180623

zbMATH Keywords

\(8\log n\)-approximationrandomized instances

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Approximation algorithms (68W25)

This page was built for publication: A greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual technique