Noon seminar
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 4560 minutes including questions.
To be kept uptodate about noon seminar presentations, please subscribe to the algoseminarl mailing list.
This is the schedule for 2019. Schedules are available between 2005 and 2019.
 Presentation
 Master's defense
 Midterm
 Invited talk
 External talk
 Practice talk
 PhD defense
 Cancelled
Upcoming talks
Send an email to Jules to schedule your talk.

Sep 04, 16:00—17:30
(Atlas 0.710)
Astrid Pieterse: Tight Parameterized Preprocessing Bounds: Sparsification via LowDegree Polynomials.

Aug 29, 16:00—17:30
(Atlas 0.710)
Thom Castermans: Algorithms for Visualization in Digital Humanities.

Aug 29, 11:00—12:30
(Atlas 0.710)
Willem Sonke: Algorithms for River Network Analysis.

Jun 27, 13:30—15:00
(Atlas 0.710)
Sándor KisfaludiBak: ETHTight Algorithms for Geometric Network Problems.

Jun 18, 12:45—13:15
(MF 12)
Martijn Struijs: Fast Distributed Algorithms for LPType Problems of Bounded Dimension.
－ Abstract
In this brief announcement we summarize our results concerning distributed algorithms for LPtype problems in the wellknown gossip model.
LPtype problems include many important classes of problems such as (integer) linear programming, geometric problems like smallest enclosing ball and polytope distance, and set problems like hitting set and set cover.
In the gossip model, a node can only push information to or pull information from nodes chosen uniformly at random.
Protocols for the gossip model are usually very practical due to their fast convergence, their simplicity, and their stability under stress and disruptions.
Our algorithms are very efficient (logarithmic rounds or better with just polylogarithmic communication work per node per round) whenever the combinatorial dimension of the given LPtype problem is constant, even if the size of the given LPtype problem is polynomially large in the number of nodes.
This is a practice talk for SPAA 2019 and joint work with Christian Scheideler and Kristian Hinnenthal.
Past talks

May 07, 12:45—13:15
(Aud 10)
Jorrick Sleijster: Clusterbased map construction: Computing representatives and intersections.
－ Abstract
In this talk, a new approach will be discussed to the GPStrajectorybased map construction problem. This new approach extends upon a current approach, which uses subtrajectory clusters to identify the underlying road segments. These subtrajectory clusters are computed for several distance parameters, from which only the stable and relevant clusters are considered. First our approach extends the subtrajectory clusters by computing a trajectory to represent the subtrajectory cluster. Based on the clusters we create a map, however, we use intersection detection to improve our final map around critical areas. An incremental approach is used, in which all bundles are added, in parts, iteratively. Our algorithms are evaluated for several domains, as we present experimental results for vehicle data, hiking data and a new domain, ski data. The results show that our algorithms are able to deal with various road widths and densely sampled, but also very sparsely sampled datasets. Furthermore, our algorithms are well able to deal with outliers and high levels of noise in the data.

Apr 23, 12:45—13:15
(MF 12)
Sándor KisfaludiBak: Hyperbolic intersection graphs and (quasi)polynomial time.
－ Abstract
We study intersection graphs of unitballlike objects in hyperbolic space. In the hyperbolic plane, we introduce a new technique to bound the treewidth of these graphs. The treewidth bounds yield quasi polynomial ($n^{O(log n)}$) algorithms for Independent Set and several other problems, while in the case of Hamiltonian Cycle and $3$Coloring we even get polynomial time algorithms. Then we will show that the quasipolynomial algorithm for Independent Set is optimal optimal up to constant factors in the exponent under ETH. If time allows, I will also talk about a separator for intersection graphs in higher dimensional hyperbolic space, and give some treewidth bounds and ETHtight algorithms.

Apr 16, 12:45—13:15
(MF 12)
Tillmann Miltzow: Smoothed Analysis of the Art Gallery Problem.
－ Abstract
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/Axs7kqL2zY.
This is joint work with: Michael Dobbins and Andreas Holmsen

Apr 02, 12:45—13:15
(MF 15)
Wouter Meulemans: Competitive Searching for a Line on a Line Arrangement.
－ Abstract
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.

Mar 12, 12:30—14:15
(MF 12)
Willem, Bram, Martijn, Dániel, Jules: EuroCG practice talks.
－ Abstract
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 VolumeBased 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

Feb 19, 12:00—12:30
(MF 12)
Jules Wulms: Topological Stability of Kinetic $k$Centers.
－ Abstract
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 solutionthe topological stability ratioconsidering 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$.

Feb 05, 16:00—17:00
(Senaatszaal)
Aleksandar Markovic: Dynamic Range and Frequency Assignment Problems.