[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
embeddings:
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
Charikar.
More information about the talks
mailing list