
Recent Posts
Archives
Categories
Meta
Monthly Archives: April 2012
Lecture 25: Online Steiner Tree
The algorithm for probabilistically embedding metric spaces into trees has numerous theoretical applications. It is a key tool in the design of many approximation algorithms and online algorithms. Today we will illustrate the usefulness of these trees in designing an … Continue reading
Posted in Uncategorized
Leave a comment
Lecture 24: Probabilistic approximation of metrics by trees
1. Probabilistic Approximation of Metrics For many optimization problems, the input data involves some notion of distance, which we formalize as a metric. But unfortunately many optimization problems can be quite difficult to solve in an arbitrary metric. In this … Continue reading
Posted in Uncategorized
Leave a comment