The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science


                            Computer Science Seminar

                                 Howard Karloff
                             AT\&T  Labs--Research


                                 will speak on


                    Approximation Algorithms for 0-EXTENSION

Abstract:
The well-known MULTIWAY CUT problem asks one to partition the vertex set of a
weighted graph into $k$ parts, where there are $k$ given terminals, each
terminal going into a different part, by cutting a set of edges of minimum
possible cost.  We will discuss 0-EXTENSION, a generalization of MULTIWAY CUT
in which cutting edge $\{u,u'\}$ and sending $u$ to terminal $t$ and $u'$ to
terminal $t'$ incurs a cost

$$   cost(u,u')*d(t,t'), $$

where $d$ is a specified metric on the terminals.  0-EXTENSION is a
generalization of Kleinberg and Tardos's METRIC LABELING problem.

I will present a linear programming-based approximation algorithm for
0-EXTENSION with a performance ratio of $O(log\ k)$, and,
 if time permits, a proof that the integrality ratio of the $LP$ is
$\Omega(\sqrt{(log\ k)})$.

This is joint work with Gruia Calinescu of IIT (Chicago) and Yuval Rabani of
the Technion.





                      The lecture will take place in the 
                     Lecture Hall, Room 1, Ziskind Building
                          on Monday, February 19, 2001
                                    at 14:30