Tuesday, 1:30am-2:20pm in EE1 045.

TITLE: Classification and Partitioning: Recent Bounds

Seffi Naor

Microsoft Research and Computer Science Dept., Technion


The Metric Labeling problem is an elegant and powerful
mathematical model capturing a wide range of classification
problems that arise in computer vision and related fields.
In a typical classification problem, one wishes
to assign labels to a set of objects to optimize some measure of the
quality
of the labeling.  The metric labeling problem captures a broad range of
classification problems where the quality of a labeling depends on the
pairwise relations between the underlying set of objects, as described
by
a weighted graph. Additionally, a metric distance function on the
labels is defined, and for each label and each vertex, an
assignment cost is given. The goal is to find a minimum-cost
assignment of the vertices to the labels. The cost of the solution
consists of two parts: the assignment costs of the vertices and
the separation costs of the edges (each edge pays its weight times
the distance between the two labels to which its endpoints are
assigned).  Metric labeling has many applications as well as
rich connections to some well known problems in combinatorial
optimization. 
The balanced metric labeling problem has an additional
constraint which upper bounds the number of vertices that can be
assigned to
each label, thus capturing various well-known balanced graph
partitioning 
problems.

In the talk I will discuss the rich body of work in approximation
algorithms,
as well as lower bounds on approximability,
that has been developed in recent years
for the metric labeling problem and its variants.