The informal research seminar of the ALGO and AGA groups. Talks last roughly 25 minutes, with five extra minutes allocated for discussion. Many presentations are focussed on recent conference presentations, or practice talks for upcoming conferences. New members are often asked to give an overview of their field of research. Talks given by invited speakers may take up to 45-60 minutes including questions.
To be kept up-to-date about noon seminar presentations, please subscribe to the algoseminar-l mailing list.
All noon seminar schedules: 2019 · 2018 · 2017 · 2016 · 2015 · 2014 · 2013 · 2012 · 2011 · 2010 · 2009 · 2008 · 2007 · 2006 · 2005
Quartile 3:
Time: Tuesday 12:45-13:15
Date | Room | Speaker | Title | |
---|---|---|---|---|
Feb 5 | Tuesday 16:00-17:00 | Senaatszaal | Aleksandar Markovic | Dynamic Range and Frequency Assignment Problems |
Feb 19 | Tuesday 12:00-12:30 | MF 12 | Jules Wulms | Topological Stability of Kinetic $k$-Centers We study the $k$-center problem in a kinetic setting: given a set of continuously moving points $P$ in the plane, determine a set of $k$ (moving) disks that cover $P$ at every time step, such that the disks are as small as possible at any point in time. Whereas the optimal solution over time may exhibit discontinuous changes, many practical applications require the solution to be stable: the disks must move smoothly over time. Existing results on this problem require the disks to move with a bounded speed, but this model is very hard to work with. Hence, the results are limited and offer little theoretical insight. Instead, we study the topological stability of $k$-centers. Topological stability was recently introduced and simply requires the solution to change continuously, but may do so arbitrarily fast. We prove upper and lower bounds on the ratio between the radii of an optimal but unstable solution and the radii of a topologically stable solution---the topological stability ratio---considering various metrics and various optimization criteria. For $k = 2$ we provide tight bounds, and for small $k > 2$ we can obtain nontrivial lower and upper bounds. Finally, we provide an algorithm to compute the topological stability ratio in polynomial time for constant $k$. |
Mar 12 | Tuesday 12:30-14:15 | MF 12 | Willem, Bram, Martijn, Dániel, Jules | EuroCG practice talks The slots at EuroCG are 15 minutes, of which about 12 should be used for the talk. In this practice session we have ~20 minutes per talk (unless things move a lot faster), so there is some time for questions and feedback. Please see estimated times below if you do not want to attend all talks. Talks in this session: ~12:30 Kinetic Volume-Based Persistence for 1D Terrains by Willem ~12:50 Maximum Physically Consistent Trajectories by Bram ~13:10 Stability analysis of kinetic oriented bounding boxes by Jules ~13:30 On the hardness of finding an average curve by Martijn ~13:50 Reliable Geometric Spanners by Dániel |
Apr 2 | Tuesday | MF 15 | Wouter Meulemans | Competitive Searching for a Line on a Line Arrangement We discuss the problem of searching for an unknown line on a known or unknown line arrangement by a searcher $S$, and show that a search strategy exists that finds the line competitively, that is, with detour factor at most a constant when compared to the situation where $S$ has all knowledge. In the case where $S$ knows all lines but not which one is sought, the strategy is $79$-competitive. We also show that it may be necessary to travel on $\Omega(n)$ lines to realize a constant competitive ratio. In the case where initially, $S$ does not know any line, but learns about the ones it encounters during the search, we give a $414.2$-competitive search strategy. |
Apr 16 | Tuesday | MF 12 | Tillmann Miltzow | Smoothed Analysis of the Art Gallery Problem In the Art Gallery Problem, we are given a polygon $P$ on $n$ vertices and a number $k$. We want to find a guard set $G$ of size $k$, such that each point in $P$ is seen by a guard in $G$. Formally, a guard $g$ sees a point $p \in P$ if the line segment $pg$ is fully contained inside $P$. We analyze the Art Gallery Problem under the lens of Smoothed Analysis. The significance of our results is that algebraic methods are not needed to solve the Art Gallery Problem in typical instances. This is the first time an $\exists\mathbb{R}$-complete problem was analyzed by Smoothed Analysis. A short video explaining the result is available at youtu.be/Axs7k-qL2zY. This is joint work with: Michael Dobbins and Andreas Holmsen |