13th Colloquium of Research Area C3C3 Kolloquium / Colloquium of the Research Area C3
by ,
Arithmeum, Lennéstr., 2 - Seminarraum
Arithmeum / Research Institute for Discrete Mathematics
09:30 - 10:00 Coffee and Tea, Room 2.075
10:00 – 10:45 Lotte Blank: Fréchet distance in the Imbalanced Case (Room 0.016)
10:45 – 11:15 Coffee break, Room 2.075
11:15 – 12:00 Hannaneh Akrami: The EFX Story: From Existence to Counterexamples (Room 0.016)
Lotte Blank: Fréchet distance in the Imbalanced Case
The Fréchet distance is a similarity measure between polygonal curves defined by $n$ and $m$ vertices. Classical algorithms 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-dimensional curves within essentially the same running time: for the discrete Fréchet distance, there is an optimal $2$-approximation algorithm, and surprisingly, for the continuous Fréchet distance in 1D, there is even an exact algorithm within this time bound. These one-dimensional running times are optimal up to logarithmic factors.
Hannaneh Akrami: The EFX Story: From Existence to Counterexamples
Envy-freeness up to any good (EFX) is one of the central notions of fairness for indivisible goods. In this talk, I will give an overview of the EFX existence problem, focusing on our positive results for three agents and, more recently, the first counterexample to the existence of EFX for submodular valuations. I will discuss the ideas behind these results and what they tell us about the frontier of EFX existence.
Heiko Röglin and László Végh