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