BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:51ec8e61-3255-43e1-96b3-b765cc7a2f65
X-WR-CALNAME:[gt.go] - 'A (1+epsilon) approximation for Ultrametric Embeddi
 ng in subquadratic time' par Gabriel Bathie
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20261025T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20241027T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20251026T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20240331T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20250330T020000
RDATE:20260329T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:51ec8e61-3255-43e1-96b3-b765cc7a2f65
DTSTAMP:20260415T232420Z
CLASS:PUBLIC
DESCRIPTION:Ultrametrics are representations of data that emphasize hierarc
 hical properties and are widely used in data visualization and clustering.
  In the Ultrametric Embedding problem\, we are given $n$ points in a metri
 c space and must output an ultrametric that best preserves the distance be
 tween points in the original data (more precisely\, we want to minimize th
 e worst-case distortion). Farach et al. gave an exact $O(n²)$-time algorit
 hm for this problem. Their algorithm is optimal\, but it does not scale to
  very large datasets. Therefore\, recent work has focused on obtaining sub
 quadratic algorithms by approximating an optimal solution for *Euclidean* 
 metrics\, resulting in a $\sqrt{2}c$-approximation algorithm that runs in 
 time $n^{1+O(1/c^2)}$. In this talk\, I will present our algorithm that ac
 hieves an arbitrarily precise approximation in subquadratic time for Eucli
 dean metrics\, namely it outputs a (1+c)-approximation of the best ultrame
 tric embedding in time $Õ(n^{1+1/c)$. \n\nOur result is based on two const
 ructions that may be of independent interest for approximation algorithms 
 on high-dimensional Euclidean data. The first is a $Õ(n^{1+1/c^2})$ time a
 lgorithm for computing a *uniformly approximate* minimum spanning tree of 
 Euclidean metrics\, using a BFS guided by Locality Sensitive Hashing (LSH)
 . The second is a dynamic data structure for approximate farthest neighbor
  in Euclidean spaces. This construction uses random projections and allows
  to i) query the farthest point in a cluster and ii) merge two clusters\, 
 both in $Õ(n^{1/c^2})$ time. \n\nJoint work with Guillaume Lagarde (LaBRI)
 . \n\n\n[Gabriel Bathie] (LaBRI) \n\nVérifiez que vous êtes bien inscrits 
 sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/
 pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmw
 iki.php/Equipes/Equipes#membres ] \n\nRemarks / Remarques \n\nFind all the
  information of the working group on this [ https://graphesetoptimisation.
 labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] . \nRetrouvez toute
 s les informations du GT sur cette [ https://graphesetoptimisation.labri.f
 r/pmwiki.php/Groupe/GT | page web ] . \n\n\n\nImport automatique depuis ht
 tps://webmel.u-bordeaux.fr/home/bf-labri.ca@u-bordeaux.fr/gt.go.ics par sy
 nc_icals_to_drupal.py pour GT-GO
DTSTART;TZID=Europe/Paris:20250117T140000
DTEND;TZID=Europe/Paris:20250117T150000
LOCATION:LaBRI/178
SEQUENCE:0
SUMMARY:[gt.go] - 'A (1+epsilon) approximation for Ultrametric Embedding in
  subquadratic time' par Gabriel Bathie
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
