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

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 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.

REFERENCES

• 1: Besag, J. 1974. Spatial interaction and the statistical analysis of lattice systems. Journal of the Royal Statistical Society B36, 2, 192--236.
• 2: Besag, J. 1986. On the statistical analysis of dirty pictures. Journal of the Royal Statistical Society B48, 3, 259--302.
• 3: 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.
• 4: Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.307-318, June 01-04, 1998, Seattle, Washington, United States
• 5: Chandra Chekuri , Sanjeev Khanna , Joseph Naor , Leonid Zosin, Approximation algorithms for the metric labeling problem via a new linear programming formulation, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.109-118, January 07-09, 2001, Washington, D.C., United States
• 6: Chvátal, V. 1979. A greedy heuristic for the set-covering problem. Math. of Oper. Res. 4, 3, 233--235.
• 7: Fernand S Cohen, Markov random fields for image modelling and analysis, Modelling and applications of stochastic processes, Kluwer, B.V., Deventer, The Netherlands, 1986
• 8: E. Dahlhaus , D. S. Johnson , C. H. Papadimitriou , P. D. Seymour , M. Yannakakis, The Complexity of Multiterminal Cuts, SIAM Journal on Computing, v.23 n.4, p.864-894, Aug. 1994 [doi>10.1137/S0097539792225297]
• 9: Dash Optimization. 2002. Xpress-MP Manual. Release 13.
• 10: Dubes, R. C. and Jain, A. K. 1989. Random field models in image analysis. Journal of Applied Statistics 16.
• 11: Freivalds, K. 2003. A nondifferentiable optimization approach to ratio-cut partitioning. In Proceedings of the 2nd Workshop on Efficient and Experimental Algorithms. Lectures Notes on Computer Science, vol. 2647. Springer-Verlag, New York.
• 12: Anupam Gupta , Éva Tardos, A constant factor approximation algorithm for a class of classification problems, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.652-658, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335397]
• 13: Kamal Jain , Mohammad Mahdian , Evangelos Markakis , Amin Saberi , Vijay V. Vazirani, Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP, Journal of the ACM (JACM), v.50 n.6, p.795-824, November 2003 [doi>10.1145/950620.950621]
• 14: Jon Kleinberg , Eva Tardos, Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.14, October 17-18, 1999
• 15: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph labeling

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Design, Experimentation

Keywords:
Approximation algorithms, graph labeling