[talks] A Karagiozova preFPO

Melissa M Lawson mml at CS.Princeton.EDU
Thu Jan 18 09:17:44 EST 2007

 Adriana Karagiozova will present her preFPO on Thursday January 25 at 3PM in Room 402.
The members of her committee are Moses Charikar, advisor; Bernard Chazelle, Bob 
Tarjan, readers; Boaz Barak, Bob Sedgewick, nonreaders.  Everyone is invited to attend 
her talk.  Her abstract follows below.

Aspects of Network Design and Metric Space Embeddings

In this talk I will present results on several problems in network design and metric space

1) Multicommodity buy-at-bulk network design We seek to design a cheap network that
satisfies the demands between the terminals of multiple source-sink pairs, where the edge
costs experience economies of scale.  We give the first non-trivial approximation
algorithm for the general case of the problem.

2) Terminal Backup
Given a graph with terminals, non-terminals and edge costs we want to find a forest that
connects each terminal to at least one other terminal.  We give a simple polynomial time
algorithm that finds the cheapest such forest.  In the process we show that a version of
3D matching, useful for tasks that involve splitting into groups of at least two members,
is solvable in polynomial time.

3) Metric Ramsey phenomena
A Ramsey theorem on metric spaces asks if given an arbitrary metric space, what is the
size of the largest subspace that embeds into $\ell_p$ with distortion at most some target
$\alpha$.  Previous work shows a phase transition at $\alpha = 2$ for $p > 2$.  We show
that such a phase transition occurs at $\alpha = 2$ for all $p \geq 1$.

4) Embedding series-parallel graphs into $\ell_1$ We give an embedding of any n-point
series-parallel metrics into $\ell_1$ with distortion O(\sqrt{\log n / \log s}), where
every coordinate of the embedding is s-Lipschitz.  Using this embedding we obtain various
other results, among which is matching the dimension-reduction lower bound of Brinkman and

More information about the talks mailing list