Balanced metric labeling

ABSTRACT

We define the balanced metric labeling problem, a generalization of the metric labeling problem, in which each label has a capacity, i.e., at most l vertices can be assigned to it. The balanced metric labeling problem is a generalization of fundamental problems in the area of approximation algorithms, e.g., arrangements and balanced partitions of graphs. It is also motivated by resource limitations in certain practical scenarios. We focus on the case where the given metric is uniform and note that this case alone encompasses various well-known graph partitioning problems. We present the first (pseudo) approximation algorithm for this problem, achieving for any ε, 0 < ε < 1, an approximation factor of O((ln n)/ε), while assigning at most min {O(ln k)/1 - ε, l + 1| ( 1 + ε) l vertices to each label (k is the number of labels). Our approximation algorithm is based on a novel randomized rounding of a linear programming formulation that combines an embedding of the graph in a simplex together with spreading metrics and additional constraints that strengthen the formulation. Our randomized rounding technique uses both a randomized metric decomposition technique and a randomized label assignment technique. At the heart of our approach is the fact that only limited dependency is created between the labels assigned to different vertices, allowing us to bound the expected cost of the solution and the number of vertices assigned to each label, simultaneously. We note that the number of vertices assigned to each label is bounded via a new inequality of Janson[15] for tail bounds of (partly) dependent random variables.

REFERENCES

• 1: N. Alon and J. Spencer. The probabilistic method. Wiley, New York, 2000.
• 2: Aaron Archer , Jittat Fakcharoenphol , Chris Harrelson , Robert Krauthgamer , Kunal Talwar , Éva Tardos, Approximate classification via earthmover metrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 3: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 4: Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
• 5: 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
• 6: 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
• 7: Julia Chuzhoy , Joseph (Seffi) Naor, The Hardness of Metric Labeling, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.108-114, October 17-19, 2004 [doi>10.1109/FOCS.2004.67]
• 8: Gruia Calinescu , Howard Karloff , Yuval Rabani, Approximation algorithms for the 0-extension problem, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.8-16, January 07-09, 2001, Washington, D.C., United States
• 9: Guy Even, Fast Approximate Graph Partitioning Algorithms, SIAM Journal on Computing, v.28 n.6, p.2187-2214, Dec. 1999 [doi>10.1137/S0097539796308217]
• 10: Guy Even , Joseph Seffi Naor , Satish Rao , Baruch Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Journal of the ACM (JACM), v.47 n.4, p.585-616, July 2000 [doi>10.1145/347476.347478]
• 11: Jittat Fakcharoenphol , Chris Harrelson , Satish Rao , Kunal Talwar, An improved approximation algorithm for the 0-extension problem, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 12: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 13: Uriel Feige , Robert Krauthgamer, A Polylogarithmic Approximation of the Minimum Bisection, SIAM Journal on Computing, v.31 n.4, p.1090-1118, 2002 [doi>10.1137/S0097539701387660]
• 14: 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]
• 15: Svante Janson, Large deviations for sums of partly dependent random variables, Random Structures & Algorithms, v.24 n.3, p.234-248, May 2004 [doi>10.1002/rsa.v24:3]
• 16: 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]
• 17: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
balanced-partition, metric-labeling