Karloff
Le Jeudi 12 Octobre 2000 à 14h30
AT&T Labs--Research
Approximation Algorithms for 0-EXTENSION
Résumé/Abstract :
The well-known MULTIWAY CUT problem asks one to partition the vertex set
V of a graph into k parts, where there are k
given terminals, each terminal going into a different part, by removing
as few edges as possible. If edges have costs, the problem is to
find a partition necessitating the cutting of a set
of edges of minimum possible cost.
However, in certain classification problems, when an edge uu' is
cut, node u being sent to terminal t and node u' to
terminal t', one pays a cost which depends not only on u and
u', but also on t, t'. Specifically, the cost is
cost(u,u')*d(t,t'),
where d(.,.) is a given metric on the terminals.
The goal is to minimize the sum of the costs paid.
For a bizarre reason (which I actually know), the problem
is called 0-EXTENSION. 0-EXTENSION is a generalization
of MULTIWAY CUT and a special case of a
classification problem posed by Kleinberg
and Tardos (and which has applications to computer vision).
I will present a linear programming-based approximation algorithm for
0-EXTENSION with a performance ratio of O(log k), and, time
permitting, a proof that the integrality ratio of the LP is
(log k)
.
We can also show (though I won't in the talk) that
there is an approximation algorithm
with a constant performance ratio for planar graphs.
(It is likely that the result for planar graphs gives
a constant-factor approximation algorithm for the
computer vision application.)
This is joint work with Gruia Calinescu of IIT (Chicago)
and Yuval Rabani of the Technion.