Tata Institute of Fundamental Research
Probabilistic Approximation of Metrics by Tree Metrics
Student Seminar
Speaker:
Nithin M. Varma
Organiser:
Sagnik Mukhopadhyay
Date:
Friday, 17 May 2013, 14:30 to 16:00
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Consider a finite set $V$ and a function $d: V \times V \rightarrow \mathbb{R}$ such that $(V,d)$ forms a metric space. A function $d_T : V' \times V' \rightarrow \mathbb{R}$ is called a tree metric on $V'$ if for all $u,v \in V'$, $d_T(u,v)$ is the length of the unique shortest path between them in $T$, where $T$ is a tree on $V'$ with nonnegative lengths on its edges. A well studied problem in literature is to approximate a given metric $d$ on $V$ using some tree metric $d_T$ on $V' \supseteq V$ in the sense that $d(u,v) \le d_T(u,v) \le \alpha d(u,v)$ for all $u,v \in V$ and for some $\alpha$. In this talk, I will present the result of Fakcharoenphol et al. that there is a randomized polynomial time algorithm which, given any metric $d$ on an $n$-sized set $V$, produces a tree metric $d_T$ on some $V' \supseteq V$, such that for all $u,v \in V$, $d(u,v) \le d_T(u,v)$ and $E[d_T(u,v)] \le O(\log n) d(u,v)$.
Reference:
A tight bound on approximating arbitrary metrics by tree metrics - Fakcharoenphol, Rao, Talwar STOC '03.
| Speaker: | Nithin M. Varma |
| Organiser: | Sagnik Mukhopadhyay |
| Date: | Friday, 17 May 2013, 14:30 to 16:00 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Consider a finite set $V$ and a function $d: V \times V \rightarrow \mathbb{R}$ such that $(V,d)$ forms a metric space. A function $d_T : V' \times V' \rightarrow \mathbb{R}$ is called a tree metric on $V'$ if for all $u,v \in V'$, $d_T(u,v)$ is the length of the unique shortest path between them in $T$, where $T$ is a tree on $V'$ with nonnegative lengths on its edges. A well studied problem in literature is to approximate a given metric $d$ on $V$ using some tree metric $d_T$ on $V' \supseteq V$ in the sense that $d(u,v) \le d_T(u,v) \le \alpha d(u,v)$ for all $u,v \in V$ and for some $\alpha$. In this talk, I will present the result of Fakcharoenphol et al. that there is a randomized polynomial time algorithm which, given any metric $d$ on an $n$-sized set $V$, produces a tree metric $d_T$ on some $V' \supseteq V$, such that for all $u,v \in V$, $d(u,v) \le d_T(u,v)$ and $E[d_T(u,v)] \le O(\log n) d(u,v)$.
Reference:
A tight bound on approximating arbitrary metrics by tree metrics - Fakcharoenphol, Rao, Talwar STOC '03.
Reference:
A tight bound on approximating arbitrary metrics by tree metrics - Fakcharoenphol, Rao, Talwar STOC '03.