Thursday, Oct 18, 2:15pm, WWH-513 (note different room)
SPEAKER:
Yuri Makarychev
TITLE:
Local Global Tradeoffs in Metric Embeddings
ABSTRACT:
Suppose that every k points in an n point metric space X are
D-distortion embeddable into l_1. We give upper and lower bounds on
the distortion required to embed the entire space X into l_1. This
is a natural mathematical question and is also motivated by the
study of relaxations obtained by lift-and-project methods for graph
partitioning problems.
In this setting, we show that X can be embedded into l_1 with
distortion O(D log (n/k)). Moreover, we give a lower bound showing
that this result is tight if D is bounded away from 1. For D = 1 +
delta we give a lower bound of Omega(log (n/k) / log (1/delta)); and
for D=1, we give a lower bound of Omega(log n/(log k + log log n)).
Our bounds improve on the results of Arora, Lovasz, Newman, Rabani,
Rabinovich and Vempala, who initiated a study of these questions.
Joint work with Moses Charikar and Konstantin Makarychev.
------------------------------------------------------------------------