BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:13th Colloquium of Research Area C3 [C3 Kolloquium / Colloquium of
  the Research Area C3]
DTSTART:20261002T073000Z
DTEND:20261002T100000Z
DTSTAMP:20260918T135900Z
UID:indico-event-1584@math-events.uni-bonn.de
DESCRIPTION:Speakers: Hannaneh Akrami\, Lotte Blank\n\n09:30 - 10:00    
   Coffee and Tea\, Room 2.075\n10:00 – 10:45    Lotte Blank: Fréchet
  distance in the Imbalanced Case (Room 0.016)\n10:45 – 11:15    Coffee
  break\, Room 2.075\n11:15 – 12:00    Hannaneh Akrami: The EFX Story: 
 From Existence to Counterexamples (Room 0.016)\n \nLotte Blank: Fréchet 
 distance in the Imbalanced CaseThe Fréchet distance is a similarity measu
 re between polygonal curves defined by $n$ and $m$ vertices. Classical al
 gorithms to compute the Fréchet distance exactly run in $\\widetilde{O}(
 nm)$ time\, and this talk focuses on recent results for the special case 
 where $m=n^\\alpha$ with $\\alpha\\in(0\,1)$. We begin with a simple $(3+
 \\varepsilon)$-approximation algorithm that runs in $\\widetilde{O}(n+m^2)
 $ time. We then show that stronger results are possible for one-dimension
 al curves within essentially the same running time: for the discrete Fré
 chet distance\, there is an optimal $2$-approximation algorithm\, and su
 rprisingly\, for the continuous Fréchet distance in 1D\, there is even a
 n exact algorithm within this time bound. These one-dimensional running t
 imes are optimal up to logarithmic factors.\nHannaneh Akrami: The EFX Stor
 y: From Existence to Counterexamples\nEnvy-freeness up to any good (EFX) i
 s one of the central notions of fairness for indivisible goods. In this t
 alk\, I will give an overview of the EFX existence problem\, focusing on 
 our positive results for three agents and\, more recently\, the first cou
 nterexample to the existence of EFX for submodular valuations. I will dis
 cuss the ideas behind these results and what they tell us about the front
 ier of EFX existence.\n\nhttps://math-events.uni-bonn.de/event/1584/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/1584/
END:VEVENT
END:VCALENDAR