{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:43:35Z","timestamp":1787323415019,"version":"build-2736575974"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2004,1]]},"abstract":"<jats:p>We consider approximation algorithms for the metric labeling problem. This problem was introduced in a paper by Kleinberg and Tardos [J. ACM, 49 (2002), pp. 616--630] and captures many classification problems that arise in computer vision and related fields. They gave an O(log k log log k) approximation for the general case, where k is the number of labels, and a 2-approximation for the uniform metric case. (In fact, the bound for general metrics can be improved to O(log k) by the work of Fakcheroenphol, Rao, and Talwar [Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 448--455].) Subsequently, Gupta and Tardos [Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, 2000, pp. 652--658] gave a 4-approximation for the truncated linear metric, a metric motivated by practical applications to image restoration and visual correspondence. In this paper we introduce an integer programming formulation and show that the integrality gap of its linear relaxation either matches or improves the ratios known for several cases of the metric labeling problem studied until now, providing a unified approach to solving them. In particular, we show that the integrality gap of our linear programming (LP) formulation is bounded by O(log k) for a general k-point metric and 2 for the uniform metric, thus matching the known ratios. We also develop an algorithm based on our LP formulation that achieves a ratio of $2+\\sqrt{2}\\simeq 3.414$ for the truncated linear metric improving the earlier known ratio of 4. Our algorithm uses the fact that the integrality gap of the LP formulation is 1 on a linear metric.<\/jats:p>","DOI":"10.1137\/s0895480101396937","type":"journal-article","created":{"date-parts":[[2005,4,26]],"date-time":"2005-04-26T21:00:46Z","timestamp":1114549246000},"page":"608-625","source":"Crossref","is-referenced-by-count":50,"title":["A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem"],"prefix":"10.1137","volume":"18","author":[{"given":"C.","family":"Chekuri","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J.","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"L.","family":"Zosin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","unstructured":"A. Archer, J. Fakcharoenphol, C. Harrelson, R. Krauthgamer, K. Talwar, and \u00c9. Tardos,\n                      Approximate classification via earthmover metrics\n                      , in Proceedings of the Fifteenth Annual ACM\u2010SIAM Symposium on Discrete Algorithms, New Orleans, LA, 2004, pp. 1072\u20131080."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"YairBartal, Probabilistic approximation of metric spaces and its algorithmic applications, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 184\u20131931450616","DOI":"10.1109\/SFCS.1996.548477"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"YairBartal, On approximating arbitrary metrices by tree metrics, ACM, New York, 1999, 161\u20131681731572","DOI":"10.1145\/276698.276725"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Y. Boykov, O. Veksler, and R. Zabih,\n                      Markov random fields with efficient approximations\n                      , in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 1998, pp. 648\u2013655.","DOI":"10.1109\/CVPR.1998.698673"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Y. Boykov, O. Veksler, and R. Zabih,\n                      Fast approximate energy minimization via graph cuts\n                      , in Proceedings of the 7th IEEE International Conference on Computer Vision, 1999, pp. 377\u2013384.","DOI":"10.1109\/ICCV.1999.791245"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Y. Boykov, O. Veksler, and R. Zabih,\n                      A new algorithm for energy minimization with discontinuities\n                      , in Proceedings of the International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, 1999.","DOI":"10.1007\/3-540-48432-9_15"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1687"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701395978"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"MosesCharikar, ChandraChekuri, AshishGoel, SudiptoGuha, Rounding via trees: deterministic approximation algorithms for group Steiner trees andk\u2010median, ACM, New York, 1999, 114\u20131231731567","DOI":"10.1145\/276698.276719"},{"key":"R10","unstructured":"J. Chuzhoy,\n                      private communication\n                      , 2001."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy and J. Naor,\n                      The hardness of metric labeling\n                      , in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2004, pp. 108\u2013114.","DOI":"10.1109\/FOCS.2004.67"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-2267-2"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1080\/02664768900000014"},{"key":"R15","unstructured":"JittatFakcharoenphol, ChrisHarrelson, SatishRao, KunalTalwar, An improved approximation algorithm for the 0\u2010extension problem, ACM, New York, 2003, 257\u20132651974928"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"J. Fakcharoenphol, S. Rao, and K. Talwar,\n                      A tight bound on approximating arbitrary metrics by tree metrics\n                      , in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 448\u2013455.","DOI":"10.1145\/780542.780608"},{"key":"R17","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1111\/j.2517-6161.1989.tb01764.x","volume":"51","author":"Greig D.","year":"1989","journal-title":"J. Roy. Statist. Soc. Ser. B"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"AnupamGupta, \u00c9vaTardos, A constant factor approximation algorithm for a class of classification problems, ACM, New York, 2000, 652\u20136582115304","DOI":"10.1145\/335305.335397"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502093"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"A.Hoffman, On simple linear programming problems, Amer. Math. Soc., Providence, R.I., 1963, 317\u201332728:1007","DOI":"10.1090\/pspum\/007\/0157778"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"H. Ishikawa and D. Geiger,\n                      Segmentation by grouping junctions\n                      , in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, 1998, pp. 125\u2013131.","DOI":"10.1109\/CVPR.1998.698598"},{"key":"R22","unstructured":"H. Ishikawa and D. Geiger,\n                      Mapping image restoration to a graph problem\n                      , in Proceedings of the 1999 IEEE\u2010EURASIP Workshop on Nonlinear Signal and Image Processing, 1999."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"DavidKarger, PhilipKlein, CliffStein, MikkelThorup, NealYoung, Rounding algorithms for a geometric embedding of minimum multiway cut, ACM, New York, 1999, 668\u20136781798090","DOI":"10.1145\/301250.301430"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1997.0154"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050040"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1145\/585265.585268"},{"key":"R27","unstructured":"S. Z. Li,\n                      Markov Random Field Modeling in Computer Vision\n                      , 2nd ed., Springer\u2010Verlag, New York, 2001."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"IoannisMilis, Task assignment in distributed systems using network flow methods, Lecture Notes in Comput. Sci., Vol. 1120, Springer, Berlin, 1996, 396\u20134051448944","DOI":"10.1007\/3-540-61576-8_98"},{"key":"R29","unstructured":"G. Monge,\n                      D\u00e9blai et Ramblai\n                      , Mem. de l\u2019Academie des Sciences, 1781."},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1109\/34.192468"},{"key":"R31","first-page":"625","volume":"29","author":"Rachev S.","year":"1984","journal-title":"Teor. Veroyatnost. i Primenen."},{"key":"R32","doi-asserted-by":"crossref","unstructured":"S. Roy and I. Cox.\n                      A maximum\u2010flow formulation of the N\u2010camera stereo correspondence problem\n                      , in Proceedings of the International Conference on Computer Vision, 1998, pp. 492\u2013499.","DOI":"10.1109\/ICCV.1998.710763"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026543900054"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480101396937","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:01:18Z","timestamp":1787320878000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480101396937"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1137\/S0895480101396937"],"URL":"https:\/\/doi.org\/10.1137\/s0895480101396937","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}