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.