Noon seminar
The informal research seminar of the ALGO group. Talks last roughly 25 minutes, with five extra minutes allocated for discussion. Many presentations are focused 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.
COVID-19 note
Some of the talks are currently conducted via Zoom. To avoid abuse, we do not distribute the join links publicly. To make the links appear in the list below, make sure you are signed in. Alternatively, you can find the join link in the announcement email.
This is the schedule for 2019. Schedules are available between 2005 and 2024.
- Presentation
- Master's defense
- Midterm
- Invited talk
- External talk
- Practice talk
- PhD defense
- Cancelled
Past talks
-
Dec 10, 12:45—13:15
(MF 13)
Rodrigo Silveira: Computing optimal shortcuts in geometric networks.
- Abstract
In this talk I will present the problem of augmenting a plane Euclidean network with a segment, called a shortcut, to minimize the largest distance between any two points along the edges of the resulting network. Problems of this type have received considerable attention recently, mostly for discrete variants of the problem. We consider here a fully continuous setting, where the problem of computing distances and placing a shortcut is much harder as all points on the network, instead of only the vertices, must be taken into account. In addition, I will briefly discuss what happens when instead of considering the largest distance of the network, the average distance is used.
-
Dec 03, 12:45—13:15
(MF 12)
Pantea Haghighatkhah: Assessment of Unsupervised Models.
- Abstract
One of the categories of machine learning is unsupervised learning. The assessment of models of this category is particularly challenging since the user lacks evidence regarding the original data set and the correct conclusions that must be made from the data set. This thesis is a pursuit for finding proper measures that can aid us in gaining insight and understanding the models. We introduce measures to evaluate the model’s performance generally and with respect to specific subsets. Hence, we find out what parts of the data were learned well by the model and what parts were overlooked. We also introduce a procedure for producing synthetic data with controlled levels of randomness to examine the models with various amounts of noise in the data. Finally, we apply our methods to various data sets and numerous models learned from them and conclude eminence of some of these models. We also point out the reasons for poor performance of the models on some of the synthetic data sets.
-
Nov 19, 12:45—13:15
(cancelled)
Pantea Haghighatkhah: Assessment of Unsupervised Models.
- Abstract
One of the categories of machine learning is unsupervised learning. The assessment of models of this category is particularly challenging since the user lacks evidence regarding the original data set and the correct conclusions that must be made from the data set. This thesis is a pursuit for finding proper measures that can aid us in gaining insight and understanding the models. We introduce measures to evaluate the model’s performance generally and with respect to specific subsets. Hence, we find out what parts of the data were learned well by the model and what parts were overlooked. We also introduce a procedure for producing synthetic data with controlled levels of randomness to examine the models with various amounts of noise in the data. Finally, we apply our methods to various data sets and numerous models learned from them and conclude eminence of some of these models. We also point out the reasons for poor performance of the models on some of the synthetic data sets.
-
Nov 12, 12:45—13:15
(MF 12)
Arthur van Goethem: Optimal Morphs of Planar Orthogonal Drawings II.
- Abstract
Van Goethem and Verbeek recently showed how to morph between two planar orthogonal drawings $\Gamma_I$ and $\Gamma_O$ of a connected graph $G$ while preserving planarity, orthogonality, and the complexity of the drawing during the morph. Necessarily drawings $\Gamma_I$ and $\Gamma_O$ must be equivalent, that is, there exists a homeomorphism of the plane that transforms $\Gamma_I$ into $\Gamma_O$. Van Goethem and Verbeek use $O(n)$ linear morphs, where $n$ is the maximum complexity of the input drawings. However, if the graph is disconnected their method requires $O(n^{1.5})$ linear morphs. In this paper we present a refined version of their approach that allows us to also morph between two planar orthogonal drawings of a disconnected graph with $O(n)$ linear morphs while preserving planarity, orthogonality, and linear complexity of the intermediate drawings.
Van Goethem and Verbeek measure the structural difference between the two drawings in terms of the so-called spirality $s = O(n)$ of $\Gamma_I$ relative to $\Gamma_O$ and describe a morph from $\Gamma_I$ to $\Gamma_O$ using $O(s)$ linear morphs. We prove that $s+1$ linear morphs are always sufficient to morph between two planar orthogonal drawings, even for disconnected graphs. The resulting morphs are quite natural and visually pleasing.
-
Oct 22, 10:00—10:45
(MF 15)
Henk Alkema: Euclidean TSP in Narrow Rectangles.
- Abstract
The Travelling Salesman Problem (TSP) is a classic NP-hard problem. A well-studied variant, also known to be NP-hard, is the Euclidean TSP, where n points are placed in a d-dimensional space, and the weight of an edge between two points is the Euclidean distance between them. In 2018, a $2^{O(n^{1-1/d})}$ algorithm was found, and it was shown that a $2^{o(n^{1-1/d})}$ algorithm does not exist unless ETH fails. On the other hand, Euclidean TSP can be trivially solved in polynomial time in $\Reals^1$. We study the complexity of Euclidean TSP in regimes between the 1-dimensional and the arbitrary 2- dimensional case. More precisely, we consider settings where the points lie in a rectangle of size $n\times\delta$ and we present algorithms that are fixed-parameter tractable for parameter $\delta$. In particular, our results are as follows. If every point $p_i$ has $x$-coordinate exactly $i$ (for $1\leq i\leq n$), and every $y$-coordinate is in the interval $[0, \delta]$, then a shortest tour can be found in $n^3 2^{O(\sqrt{\delta} \log \delta)}$ time. Furthermore, if the $n$ points are distributed uniformly at random, i.i.d., in a rectangle of size $n\times\delta$, a shortest tour can be found in expected time $n^4 2^{O(\delta \log \delta)}$.
-
Oct 15, 14:00—14:30
(MF 14)
Rik Sweep: Homology of Moving Points.
- Abstract
Topological data analysis is an area of research that is concerned with the shape of data. It has applications in for instance machine learning, biology and geographic data analysis. Homology tries to capture the shape of data by computing and characterizing the holes in the data. In this thesis, we study the shape of moving data. We present a data structure that captures the homology of the points once, and maintains it throughout a simulation of the points by updating the structure whenever it should change.
In this thesis we present a kinetic data structure for computing and maintaining the homology of a set $S$ of $n$ moving balls of fixed radius in $\mathbb{R}^d$. This kinetic data structure consists of two parts. The first part is a kinetic data structure that maintains the $d$-dimensional $\alpha$-complex, which is a shape equivalent to the union of balls. This data structure is efficient, but need not be responsive, local or compact. The second part is a dynamic data structure that maintains the homology of a dynamically changing simplicial complex. This data structure has update time roughly quadratic in the number of simplices and uses space linear in the number of simplices. We also present ways to speed up the maintenance of the homology in specific dimensions and we present a method to disregard exterior events in the center of clusters.
-
Sep 30, 12:00—12:30
(Traverse 0.30 (Room 2))
Aleksandr Popov: Similarity of Uncertain Trajectories.
- Abstract
In this presentation, we discuss similarity of uncertain trajectories, with the focus on region-based uncertainty models for measurement (disks, line segments, sets of points) and discrete and continuous Fréchet distance.
We show that finding upper bound on both discrete and continuous Fréchet distance on uncertain trajectories is an NP-complete problem in many settings.
We also study expected discrete and continuous Fréchet distance, assuming uniform distribution of points within the uncertainty regions, and show that finding it in many settings is #P-hard.
Finally, we discuss the setting with time bands, where we enforce temporal similarity of the two trajectories, thus decreasing the problem complexity, and give the polynomial-time algorithms to find upper bound and expected value of discrete and continuous Fréchet distance in this setting for trajectories with uncertainty model of sets of points.
-
Sep 10, 14:00—14:30
(Atlas 11.201)
Erik Reusken: Algorithms for parallel machine scheduling with a sequence dependent cost function.
-
Sep 04, 16:00—17:30
(Atlas 0.710)
Astrid Pieterse: Tight Parameterized Preprocessing Bounds: Sparsification via Low-Degree Polynomials.
-
Aug 30, 14:00—14:30
(MF 3.141)
Maurits Ambags: Exact Algorithms for Domination Problems Parameterized by Tree-depth using Polynomial Space.
- Abstract
Parameterized algorithms offer a way to efficiently compute solutions to large NP-hard
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 tree-depth in O*(3^td) time, introduced by Pilipczuk and Wrochna [30]. While tree-depth
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 tree-depth of
the input graph.
-
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.
-
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 El-Assady: 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 highly-edited text data (e.g., literary, scientific, and technical publications), verbatim text transcripts contain non-standard 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 human-in-the-loop 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://el-assady.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 Triple-free Deletion}, \textsc{Wheel-free Deletion} among others. We show that both the vertex and edge deletion variant of the \textsc{Almost Wheel-free 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 One-Round 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 One-Round Discrete Voronoi Game.
-
Jun 27, 13:30—15:00
(Atlas 0.710)
Sándor Kisfaludi-Bak: ETH-Tight Algorithms for Geometric Network Problems.
-
Jun 18, 12:45—13:15
(MF 12)
Martijn Struijs: Fast Distributed Algorithms for LP-Type Problems of Bounded Dimension.
- Abstract
In this brief announcement we summarize our results concerning distributed algorithms for LP-type problems in the well-known gossip model.
LP-type 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 LP-type problem is constant, even if the size of the given LP-type 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: Cluster-based map construction: Computing representatives and intersections.
- Abstract
In this talk, a new approach will be discussed to the GPS-trajectory-based 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 Kisfaludi-Bak: Hyperbolic intersection graphs and (quasi-)polynomial time.
- Abstract
We study intersection graphs of unit-ball-like 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 quasi-polynomial 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 ETH-tight 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/Axs7k-qL2zY.
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 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
-
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 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$.
-
Feb 05, 16:00—17:00
(Senaatszaal)
Aleksandar Markovic: Dynamic Range and Frequency Assignment Problems.