Metric clustering via consistent labeling

ABSTRACT

We design approximation algorithms for a number of fundamental optimization problems in metric spaces, namely computing separating and padded decompositions, sparse covers, and metric triangulations. Our work is the first to emphasize relative guarantees, that compare the produced solution to the optimal one for the input at hand. By contrast, the extensive previous work on these topics has sought absolute bounds that hold for every possible metric space (or for a family of metrics). While absolute bounds typically translate to relative ones, our algorithms provide significantly better relative guarantees, using a rather different algorithm.

Our technical approach is to cast a number of metric clustering problems that have been well studied---but almost always as disparate problems---into a common modeling and algorithmic framework, which we call the consistent labeling problem. Having identified the common features of all of these problems, we provide a family of linear programming relaxations and simple randomized rounding procedures that achieve provably good approximation guarantees.

REFERENCES

• 1: {AP90} B. Awerbuch and D. Peleg. Sparse partitions. In 31st Annual IEEE Symposium on Foundations of Computer Science, pages 503--513, 1990.
• 2: {Ass82} P. Assouad. Sur la distance de nagata. C. R. Acad. Sci. Paris Ser. I Math., 1(294):31--34, 1982.
• 3: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 4: {Bar04} Y. Bartal. Graph decomposition lemmas and their role in metric embedding methods. In 12th Annual European Symposium, volume 3221 of Lecture Notes in Computer Science, pages 89--97. Springer, 2004.
• 5: Mihai Bǎdoiu , Piotr Indyk , Anastasios Sidiropoulos, Approximation algorithms for embedding general metrics into trees, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.512-521, January 07-09, 2007, New Orleans, Louisiana
• 6: {BK07} Y. Bartal and R. Krauthgamer. Private communication, 2007.
• 7: Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha , Serge Plotkin, Approximating a Finite Metric by a Small Number of Tree Metrics, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.379, November 08-11, 1998
• 8: Gruia Călinescu , Howard Karloff , Yuval Rabani, An improved approximation algorithm for MULTIWAY CUT, Journal of Computer and System Sciences, v.60 n.3, p.564-574, June 2000 [doi>10.1006/jcss.1999.1687]
• 9: Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation Algorithms for the 0-Extension Problem, SIAM Journal on Computing, v.34 n.2, p.358-372, 2005 [doi>10.1137/S0097539701395978]
• 10: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, v.69 n.3, p.485-497, November 2004 [doi>10.1016/j.jcss.2004.04.011]
• 11: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 12: James D. Guyton , Michael F. Schwartz, Locating nearby copies of replicated Internet servers, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.288-298, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 13: Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications, SIAM Journal on Computing, v.25 n.2, p.235-251, February 1996 [doi>10.1137/S0097539793243016]
• 14: Robert Krauthgamer , James R. Lee, Navigating nets: simple algorithms for proximity search, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 15: Robert Krauthgamer , James R. Lee, Algorithms on negatively curved spaces, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.119-132, October 21-24, 2006 [doi>10.1109/FOCS.2006.9]
• 16: {KLMN05} R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: A new embedding method for finite metrics. Geometric And Functional Analysis, 15(4):839--858, 2005.
• 17: Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
• 18: Robert Krauthgamer, On triangulation of simple networks, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248380]
• 19: Claire Kenyon , Yuval Rabani , Alistair Sinclair, Low distortion maps between point sets, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007398]
• 20: Jon Kleinberg , Aleksandrs Slivkins , Tom Wexler, Triangulation and Embedding Using Small Sets of Beacons, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.444-453, October 17-19, 2004 [doi>10.1109/FOCS.2004.70]
• 21: Jon Kleinberg , Éva Tardos, Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields, Journal of the ACM (JACM), v.49 n.5, p.616-639, September 2002 [doi>10.1145/585265.585268]
• 22: {LLR95} N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 23: {LN03} J. R. Lee and A. Naor. Metric decomposition, smooth measures, and clustering. Preprint, September 2003.
• 24: {LR88} F. T. Leighton and S. Rao. An approximate maxflow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In 29th Annual Symposium on Foundations of Computer Science, pages 422--431, October 1988.
• 25: {LS93} N. Linial and M. Saks. Low diameter graph decompositions. Combinatorica, 13(4):441--454, 1993.
• 26: {LS05} U. Lang and T. Schlichenmaier. Nagata dimension, quasisymmetric embeddings, and lipschitz extensions. International Mathematics Research Notices, 2005(58):3625--3655, 2005. doi:10.1155/IMRN.2005.3625.
• 27: Satish Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, Proceedings of the fifteenth annual symposium on Computational geometry, p.300-306, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304983]
• 28: Aleksandrs Slivkins, Distance estimation and object location via rings of neighbors, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073823]
• 29: Aleksandrs Slivkins, Distributed approaches to triangulation and embedding, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 30: Kunal Talwar, Bypassing the embedding: algorithms for low dimensional metrics, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007399]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
      G.1.6 Optimization
          Subjects: Linear programming

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory