The input to the balanced metric labeling problem is an undirected weighted graph $G$, a metric $d$ defined on a label set $L$, and a capacity upper bound $\ell$. The goal is to find a minimum cost labeling of the vertex set of $G$, where the cost of a labeling comprises of two terms. The first term is the sum of assigning the labels to the vertices, and the second term is the sum, taken over all edges, of the edge weight multiplied by the metric distance between the labels assigned to the two endpoints of the edge. In addition, the number of vertices that can be assigned to a label is bounded by $\ell$. The balanced metric labeling problem is a natural generalization of fundamental problems in the area of approximation algorithms, e.g., metric labeling, arrangements, and balanced partitions of graphs. It is also motivated by resource limitations in certain practical scenarios. Our main focus is on the case where the given metric is uniform which already captures various well-known graph partitioning problems. The main result is the first (pseudo) approximation algorithm for this problem, achieving for any $\epsilon$, $0<\epsilon <1$, an approximation factor of $O\left( \frac{\ln n}{\epsilon}\right)$, while assigning at most $\min \left\{ \frac{O(\ln k)}{1-\epsilon},\ell +1 \right\} \left( 1+\epsilon\right) \ell$ vertices to each label ($k$ is the number of labels). The 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 constraints and additional constraints that strengthen the formulation. The randomized rounding technique uses both a randomized metric decomposition technique and a randomized label assignment technique. We note that the number of vertices assigned to each label is bounded via a new inequality of Janson for tail bounds of (partly) dependent random variables.

Joint work with Roy Schwartz.