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.