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.

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

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

Aug 30, 14:00—14:30
()
Maurits Ambags: Exact Algorithms for Domination Problems Parameterized by Treedepth using Polynomial Space.
－ Abstract
Parameterized algorithms offer a way to efficiently compute solutions to large NPhard
problem instances as long as these instances are simple with respect to some quanti fiable
parameter. We study an algebraic technique used to count Dominating Sets parameterized
by treedepth in O*(3^td) time, introduced by Pilipczuk and Wrochna [30]. While treedepth
is a relatively unexplored structural parameter compared to related parameters
treewidth and pathwidth, here it excels in guaranteeing fully polynomial space usage.
This is a valuable property since often computer memory is more strictly limited than
computation time. We show how and why this technique works, apply it to solve related
domination problems such as Independent Dominating Set using O*(3^td) time and Total
Dominating Set using O*(4^td) time, again using polynomial space, and show problems
where this technique likely fails to perform efficiently.
We also explore a related technique for Dynamic Programming using polynomial space
based on subset convolutions and repeat an algorithm by Fürer and Yu [19] acting upon
tree decompositions that curiously has a time complexity depending on the treedepth of
the input graph.

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

Aug 06, 12:45—13:15
(MF 3.141)
Juri Buchmüller: Cutting the Edge: Making room on maps without overplotting map features.
－ Abstract
Adding spatial information on geographical maps visually mostly implies at least some overplotting of map features. SpaceCuts and SurgeryCuts provide two approaches for putting additional visualizations on maps without occlusion of other map features by introducing and extending cuts into the map.

Aug 05, 11:30—12:30
(MF 3.141)
Mennatallah ElAssady: Visual interactive analysis of verbatim text transcripts.
－ Abstract
Verbatim text transcripts capture the rapid exchange of opinions, arguments, and information among participants of a conversation. As a form of communication that is based on social interaction, multiparty conversations are characterized by an incremental development of their content structure. In contrast to highlyedited text data (e.g., literary, scientific, and technical publications), verbatim text transcripts contain nonstandard lexical items and syntactic patterns.
Thus, analyzing these transcripts automatically introduces multiple challenges.
In this talk, I will present approaches developed (in context of the LingVis.io framework) to enable humanities and social science scholars to get different perspectives on verbatim text data in order to capture strategies of successful rhetoric and argumentation. To analyze why specific discourse patterns occur in a transcript, three main pillars of communication are studied through answering the following
questions: (1) What is being said? (2) How is it being said? (3) By whom is it being said?
In addition to reporting on visualization techniques for the analysis of conversation dynamics, I will argue for the importance of tuning automatic content analysis models to unique textual characteristics, appearing, for example, in verbatim text transcripts. In particular, I will present a visual analytics framework for the progressive learning of topic modeling parameters, as well as discuss approaches for explainable Artificial Intelligence. Our humanintheloop process simplifies the model tuning task through intuitive user feedback on the relationship between topics and documents.
Example Case Study: http://lingvis.io/
Personal Website: https://elassady.com/

Jul 17, 13:00—13:30
(MF 14)
Jari de Kroon: Polynomial kernels for structural parameterizations of deletion into perfect graphs and related graph classes.
－ Abstract
In parameterized complexity, a kernel is the result of a kernelization algorithm. Such an algorithm reduces an input of a parameterized problem to an equivalent instance whose size is bounded by a function of a parameter that is part of the input. Smaller kernels are more useful in practice, therefore a large part of kernelization research is concerned with achieving linear or polynomial size kernels. Vertex deletion problems are often investigated in the parameterized setting. We wonder whether we can delete a small number of vertices such that the resulting graph satisfies a certain property. We investigate the vertex deletion problem parameterized by the size of a minimum vertex cover of the input graph. We give polynomial kernels for \textsc{Perfect Deletion}, \textsc{Asteroidal Triplefree Deletion}, \textsc{Wheelfree Deletion} among others. We show that both the vertex and edge deletion variant of the \textsc{Almost Wheelfree Deletion} problem do not admit a polynomial kernel unless coNP $\subseteq$ NP/poly.

Jul 10, 14:00—14:30
(MF 3.141)
Niek van Hulzen: Experimental work on Discrete Voronoi Game.
－ Abstract
The OneRound Discrete Voronoi Game consists of a set V of n voters represented by points in the plane and two integers k and l. There are two players, Player 1 and Player 2, who will be able to place k and l facilities respectively. First, Player 1 places k facilities, then Player 2 places l facilities. A voter v in V is won by Player 1 when the Euclidean distance of v to the nearest facility of Player 1 is smaller than the Euclidean distance of v to the nearest facility of Player 2, and similarly for Player 2. The player who wins most voters will then win the OneRound Discrete Voronoi Game.

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.

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.