BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/365
DTSTAMP:20230914T125921Z
SUMMARY:Probabilistic Approximation of Metrics by Tree Metrics
DESCRIPTION:Speaker: Nithin M. Varma\n\nAbstract: \nConsider 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$\, w
 here $T$ is a tree on $V'$ with nonnegative lengths on its edges. A well s
 tudied problem in literature is to approximate a given metric $d$ on $V$ u
 sing 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 a
 l. 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)$.\nReference: \nA tight bo
 und on approximating arbitrary metrics by tree metrics - Fakcharoenphol\, 
 Rao\, Talwar STOC '03.\n\n \n\n \n
URL:https://www.tcs.tifr.res.in/web/events/365
DTSTART;TZID=Asia/Kolkata:20130517T143000
DTEND;TZID=Asia/Kolkata:20130517T160000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR