{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,10]],"date-time":"2023-01-10T13:27:25Z","timestamp":1673357245788},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2005,12,31]]},"abstract":"\n 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\n n<\/jats:italic>\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.\n <\/jats:p>","DOI":"10.1145\/1064546.1180623","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":2,"title":["A greedy approximation algorithm for the uniform metric labeling problem analyzed by a primal-dual technique"],"prefix":"10.1145","volume":"10","author":[{"given":"Evandro C.","family":"Bracht","sequence":"first","affiliation":[{"name":"Universidade Estadual de Campinas, Campinas--SP, Brazil"}]},{"given":"Luis A. A.","family":"Meira","sequence":"additional","affiliation":[{"name":"Universidade Estadual de Campinas, Campinas--SP, Brazil"}]},{"given":"F. K.","family":"Miyazawa","sequence":"additional","affiliation":[{"name":"Universidade Estadual de Campinas, Campinas--SP, Brazil"}]}],"member":"320","published-online":{"date-parts":[[2005,12,31]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"192","article-title":"Spatial interaction and the statistical analysis of lattice systems","volume":"36","author":"Besag J.","year":"1974","journal-title":"Journal of the Royal Statistical Society"},{"key":"e_1_2_1_2_1","first-page":"259","article-title":"On the statistical analysis of dirty pictures","volume":"48","author":"Besag J.","year":"1986","journal-title":"Journal of the Royal Statistical Society"},{"key":"e_1_2_1_3_1","unstructured":"Bracht Evandro C. Meira Luis A. A. and Miyazawa F. K. 2002. Instances and programs to Uniform Metric Labeling Problem. http:\/\/www.ic.unicamp.br\/~aprox\/labeling. Bracht Evandro C. Meira Luis A. A. and Miyazawa F. K. 2002. Instances and programs to Uniform Metric Labeling Problem. http:\/\/www.ic.unicamp.br\/~aprox\/labeling."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276332"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 109--118","author":"Chekuri C."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Cohen F. S. 1986. Markov random fields for image modelling and analysis. Modelling and Applications of Stochastic Processes. 243--272. Cohen F. S. 1986. Markov random fields for image modelling and analysis. Modelling and Applications of Stochastic Processes. 243--272.","DOI":"10.1007\/978-1-4613-2267-2_10"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"e_1_2_1_9_1","unstructured":"Dash Optimization. 2002. Xpress-MP Manual. Release 13. Dash Optimization. 2002. Xpress-MP Manual. Release 13."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1080\/02664768900000014"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1764149.1764160"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335397"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/950620.950621"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 40th Annuall IEEE Symposium on Foundations of Computer Science. 14--23","author":"Kleinberg J."},{"key":"e_1_2_1_15_1","unstructured":"Vazirani V. 2001. Approximation Algorithms. Springer-Verlag New York. Vazirani V. 2001. Approximation Algorithms. Springer-Verlag New York."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1064546.1180623","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T12:10:38Z","timestamp":1672229438000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1064546.1180623"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12,31]]},"references-count":15,"alternative-id":["10.1145\/1064546.1180623"],"URL":"http:\/\/dx.doi.org\/10.1145\/1064546.1180623","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12,31]]}}}