Noon seminar

The informal research seminar of the ALGA 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.

This is the schedule for 2022. Schedules are available between 2005 and 2022.

• Presentation
• Master's defense
• Midterm
• Invited talk
• External talk
• Practice talk
• PhD defense
• Cancelled

Upcoming talks

Send an email to Alex to schedule your talk.

• Dec 16, 16:00—17:00 (Atlas 0.710 and Teams)
  Bram Custers: Algorithms for Context-Aware Trajectory Analysis.

Past talks

• Oct 19, 13:00—13:40 (MF 15)
  Thijs Beurskens: Towards Dynamic River Networks.
  － Abstract
  

  Rivers are one of the main contributors to the shape of the landscape, and they are often unpredictable and can cause floods and landslides. To understand how a river evolves, we want to find methods to analyse the complex behaviour of rivers, but before we can find such methods, we need a way to represent a time-varying river. As of now, there are no satisfying automated ways to extract an abstract time-varying representation of a time-varying river, based on DEMs of the input terrain. Therefore, we propose two models for dynamic river networks, which capture the changing channel structure in evolving rivers, by matching features over subsequent time steps. The first model is based on the use of a similarity measure, comparing channels, and the second model is based on the use of a displacement field, describing the evolution of the terrain. To find adequate models for such measures and displacement fields, we use various existing techniques, such as a volume-based similarity measure, and the theory of optimal transport, to experimentally find desirable channel matchings. The two proposed models for a dynamic river network provide two promising building blocks that can lead to a desirable representation of a time-varying river. Moreover, through the process of modelling such networks, we identify and pose some of the key challenges in pursuing algorithms for the construction of a dynamic river network.

• Sep 29, 12:00—12:40 (MF 3.122)
  Cosmin-Marian Popa: Video Summarization Using Unsupervised Learning.
  － Abstract
  

  Video summarization is the problem of selecting segments of a video, such that those segments represent the most important events. Indeed, the goal in the video summarization task is to facilitate large-scale video browsing by producing short, concise summaries that are diverse and representative of original videos. In this thesis, we propose an unsupervised video summarization framework based on clustering (both flat and hierarchical) and object detection. We evaluate our video summarization framework by comparing the created automated summaries to human-made summaries. Compared to VSumm, a popular video summarization technique on which our framework is based, our approach provides better results on average on the tested datasets. Additionally, we provide a visualization method based on agglomerative clustering that presents video summaries on multiple levels of detail in a tree format.

• Sep 26, 13:00—13:40 (MF 6.131)
  Ruben Heek: Streaming and Distributed Anomaly Detection and its Applications.
  － Abstract
  

  Anomaly detection is the problem of finding unexpected patterns in data. With the growing size of data being generated, it becomes increasingly difficult to detect anomalies, especially when the data: (i) is given in a streaming fashion and needs to be processed in real-time or using small space; (ii) is distributed among many many machines for which the communication bottleneck ought to be reduced. This thesis proposes the use of Random Shift Forest (RSF), a simple yet powerful isolation-based anomaly detector, and discusses how it can be extended to a wide variety of models and data. Various versions of streaming and distributed RSF are formalised, and their performance is analysed and empirically verified. In doing so, this thesis develops a broadly applicable anomaly detection framework to use and build upon.

• Sep 14, 16:00—17:00 (Atlas 0.710 and Teams)
  Huib Donkers: Parameterized Algorithms for Finding Large Sparse Subgraphs: Kernelization and Beyond.
• Sep 08, 10:30—11:10 (MF 15)
  Stefan Tanja: The Practicality of Reduction Rules for the Directed Feedback Vertex Set Problem.
  － Abstract
  

  Kernelizations have been used as a form of preprocessing for NP-hard problems, to enable the usage of exact methods, such as Integer Linear Programming (ILP) algorithms, by shrinking the input as much as possible. The application of kernelizations is mostly theoretical, so it is relatively unclear how practical kernelizations are, and when they enable the practical use of exact algorithms. In this thesis we investigate how effective kernelizations are in obtaining practical exact algorithms. We focus on the Directed Feedback Vertex Set problem. We design and implement a kernelization, together with an ILP-based algorithm, and a Branch & Bound algorithm, which both use our kernelization. We then evaluate both algorithms with and without reductions, and we submit our best performing algorithm to the Parameterized Algorithms and Computational Experiments challenge to evaluate its performance. We determine that reductions certainly can accelerate an exact algorithm, such as a Branch & Bound algorithm, but already practical ILP-based algorithms can be obtained in conjunction with a strong ILP solver without applying any reductions at all.

• Sep 07, 10:30—11:10 (MF 6.131)
  Arturs Remesis: Flow Map Layout via Height Map Manipulation.
  － Abstract
  

  Flow maps are used to visualize the flow of objects, such as the migration of people and the export of goods, between geographic locations. A good flow map avoids visual clutter, merges lines smoothly, and avoids crossing its own edges and obstacles.
  
  This thesis proposes a new model that generates flow maps of good visual quality by using an iterative height map approach. Our model computes a downhill flow of paths and merges them by carving the terrain such that the paths are pushed closer to each other. The height map can be easily extended with additional constraints such as obstacles. We also provide improvements in path computation by interpolating elevation in the height map.
  
  We investigate the effects our various components have on the resulting flow map with extensive experimentation. Our results show that the height map approach yields flow map skeletons of good visual quality and has the potential for further extensions.

• Aug 30, 15:00—15:40 (MF 14)
  Thomas Gian: Transforming Geographic Boundaries to Prevent Symbol Overlap.
  － Abstract
  

  In this project, we discuss proportional symbol maps, which represent a quantitative variable shown in the size of the symbol. For these maps, it is of importance that individual symbols can be recognized distinctly and that their relative sizes can be judged. An undesirable yet common occurrence is the overlap between symbols, which we aim to completely prevent. One approach is to minimize the displacement of the symbols so that there is no overlap, leaving the corresponding represented feature unchanged. We approach this problem by allowing the shape of the corresponding represented feature to be transformed. We first model the problem and then we design and implement an algorithm, which we then evaluate through various experiments.

• Aug 04, 10:30—11:10 (MF 15)
  Sean McCarren: Analyzing Adverse Events of Drugs.
  － Abstract
  

  Prediction of the risks of adverse events from drug treatments is essential, but the explainability and even interpretability of these predictions are often disregarded. In collaboration with a research group from Amsterdam UMC that created the ‘Toxicity Atlas’, which is a combined approach that both predicts and visualizes the adverse events of drug treatments, we have the objective of both evaluating and improving their work where possible. Their approach presents interesting ideas that clinicians wish for, however, we find that the approach shows poor performance on our quantitative assessment, after which various technical issues were found that can explain this poor performance. We are able to improve the visualization of adverse events by making use of the clinical definitions of adverse events to relate and group adverse events. We additionally improve the interpretability of this visualization by redesigning the visualization, as well as summarizing the adverse events. We use quantitative measures as well as compelling examples to argue that our visualization better achieves the objectives set by our collaborators. We hope our visualization may be helpful to clinicians and benefit the assessment of predicted risks of drug treatments.

• Jul 25, 15:00—15:40 (MF 6.132)
  Menno Theunis: Experimental Analysis of Algorithms for the Dynamic Graph Coloring Problem.
  － Abstract
  

  This thesis focuses on the dynamic graph coloring problem, a dynamic variant based on the well-researched graph coloring problem. This variant of the problem not only considers the number of colors used in the coloring for a graph, but also how many nodes in this graph need to change their color when the graph is changed. The balance between these two measures of quality, as well as running time, creates an inherent trade-off, in which algorithms solving this problem often only focus on one or the other. A variety of such algorithms already exist and are compared, as well as improved upon, in this thesis. Each of these algorithms uses different variables to measure its effectiveness, making it difficult to compare their advantages and disadvantages. Finding the right option for a practical application is thus unnecessarily difficult. By implementing the different algorithms and comparing them experimentally, we get a better insight of the strong and weak points of these algorithms. Using this knowledge we propose two new improved variants of these algorithms, obtained by combining aspects of the existing ones. We find that this approach of combining existing algorithms with different strong points often yields superior results and allows for a more versatile trade-off within the algorithm, making it suitable for a broader range of practical applications.

• Jul 11, 15:30—16:10 (MF 14 and Zoom)
  Jaime Venne: Designing (1 + ε)-Certified Algorithms for Planar Optimization Problems with Local Feasibility Properties.
  － Abstract
  

  Angelidakis, Awasthi, Blum, Chatziafratis, and Dan recently obtained a $(1 + ε)$-certified algorithm (with $ε > 0$) for the planar maximum weight independent set problem with integer polynomially-bounded weights. The algorithm runs in $|V(G)|^{Ω(1/ε)}$ time and we deem its underlying combinatorial properties as difficult to generalize to similar problems. Therefore, we explored opportunities to obtain an algorithm with an improved running time, which can also be easily generalized to similar problems. We contribute by proposing a $(1 + ε)$-certified algorithm that runs in $W · f(m/ε) · |V(G)|^{O(1)}$ time for each problem on connected planar graphs with integer weights that satisfies the conditions of a notion we introduce as $m$-locally planar optimized. Here $W$ equals the sum of the input weights, and $m ≥ 1$ is equal to $1$ for the minimum weight vertex cover problem, $2$ for the minimum weight dominating set problem, and a constant for each fixed $H$ of the minimum weight $H$-Subgraph-Deletion problem. A linear-time reduction from the minimum weight vertex cover problem obtains our $(1 + ε)$-certified algorithm for the maximum weight independent set problem. Our algorithm is inspired by Baker’s technique for building polynomial time approximation schemes for problems on planar graphs. Starting from a trivial solution, our iterative algorithm repeatedly makes local improvements in induced subgraphs that have a treewidth of $O(m/ε)$. When no further improvements of this form can be made, we use a stronger notion of the pigeonhole principle to prove that the resulting solution is optimal for a $(1 + ε)$-perturbation of the weight function.

• Jul 08, 11:00—11:40 (MF 2)
  Geert van Wordragen: New Results for Discrete Voronoi Games.
  － Abstract
  

  In the one-round discrete Voronoi game, two players compete over a set of voters represented by points $V ⊂ R^d$. They do this by placing points: Player 1 places $k$ points, followed by Player 2 placing $ℓ$ points, after which each voter is won by the player that placed a point closest to it. For three different definitions of ‘closest’, we present lower bounds on the number of voters Player 1 wins under optimal play of the game in $R^2$ with $ℓ = 1$. Such bounds already existed when ‘closest’ is based on the $L_2$ metric, so there we prove better bounds with an algorithm based on the quadtree of $V$. We also introduce bounds for the $L_1$ metric and for the personalised $L_1$ metric, where each voter has a preference vector describing how they value the distance in each coordinate.

• Jul 05, 10:30—11:30 (MF 15 and Zoom)
  Ruben Verhaegh: The Parameterized Complexity of a New Matching Problem: The Paired Matching Problem.
  － Abstract
  

  We introduce a new matching problem originating from industry called the Paired Matching problem. The objective in the problem is to find a maximum matching of minimum cost in a bipartite graph. This is complicated by a non-trivial definition of cost, which is expressed based on a pairing of the vertices in one partite set. We prove that the problem is NP-complete, but also give some special cases of the problem which can be solved in polynomial time. We also study the parameterized complexity of various parameterizations of the problem. These include parameterizations by the solution size and by different measures for the density or complexity of the graph. For most of these, we provide parameterized algorithms to show that these parameterizations are either in FPT or in XP. For a parameterization of particular practical interest, we give a randomized XP algorithm by generalizing a result known for the Exact Matching problem.

• Jun 27, 11:30—12:00 (MF 13)
  Sampson Wong: Improving the Dilation of a Metric Graph by Adding Edges.
  － Abstract
  

  Most of the literature on spanners focuses on building the graph from scratch. This paper instead focuses on adding edges to improve an existing graph. A major open problem in this field is: given a graph embedded in a metric space, and a budget of $k$ edges, which $k$ edges do we add to produce a minimum-dilation graph? The special case where $k = 1$ has been studied in the past, but no major breakthroughs have been made for $k > 1$. We provide the first positive result, an $O(k)$-approximation algorithm that runs in $O(n^3 \log n)$ time.

• Jun 27, 11:00—11:30 (MF 13)
  Jad Bassil: Self-Reconfiguration for Modular Robotic Programmable Matter Using a Porous Structure.
  － Abstract
  

  I will present 3D Catoms and how they can be arranged in a porous structure to improve self-reconfiguration by allowing parallel flow of modules inside of the structure without collisions or blocking. Then, present a self-reconfiguration algorithm based on max-flow search to transform the structure into a given goal shape.

• Jun 24, 13:00—13:40 (MF 15)
  Kees Voorintholt: Efficient and Robust Distributed Algorithms for Minimum Spanning Tree.
  － Abstract
  

  Clustering of data plays a central role in Computer Science. Particular applications are recommendation engines, search engines, and image segmentation to name a few. Minimum Spanning Tree (MST)-based algorithms are among the most popular clustering algorithms. This includes agglomerative clustering, Cure, and affinity clustering. However, the amount of data to analyze is increasing at a very fast rate every day. Hence there is a need for new solutions to efficiently compute effective different variations of the classical hierarchical clustering on BigData. The current distributed clustering algorithms, based on building a Minimum Spanning Tree have two weaknesses:
  • MST-based clustering algorithms are not space and work efficient.
  • They are not robust against sudden changes in the network and even a small change can completely change the shape of these clusterings.
  
  In this thesis, we address these issues. In particular, we have the following results:
  • We obtain the first space and work efficient distributed algorithm for the MST problem in dense networks (in the MapReduce model).
  • We benchmark the performance of our distributed algorithm against well-known distributed algorithms using synthetic datasets and real-world social networks and observe that the communication complexity of our algorithm is the smallest among these algorithms.
  • We propose an optimization of the affinity clustering algorithm (i.e., distributed implementation of Borůvka's algorithm for MST problem) where we randomly perturb edge weights and classify the perturbed edges in a logarithmic number of buckets and we empirically show that this improved affinity clustering is more robust against small changes in networks.

• Jun 20, 13:00—14:00 (MF 15)
  Tom Peters: On the Computational Power of Energy-Constraint Mobile Robots: Algorithms and Cross-Model Analysis.
  － Abstract
  

  The talk is 25 minutes, the rest is scheduled for questions and feedback.
  
  We consider distributed systems of identical autonomous computational entities, called robots, moving and operating in the plane in synchronous Look–Compute–Move (LCM) cycles. The algorithmic capabilities of these systems have been extensively investigated in the literature under four distinct models (Oblot, FSta, FCom, Lumi), each identifying different levels of memory persistence and communication capabilities of the robots. Despite their differences, they all always assume that robots have unlimited amounts of energy.
  
  In this paper, we remove this assumption and start the study of the computational capabilities of robots whose energy is limited, albeit renewable. We first study the impact that memory persistence and communication capabilities have on the computational power of such energy-constrained systems of robots; we do so by analyzing the computational relationship between the four models under this energy constraint. We provide a complete characterization of this relationship.
  
  We then study the difference in computational power caused by the energy restriction and provide a complete characterization of the relationship between energy-constrained and unrestricted robots in each model. We prove that within Lumi there is no difference; an integral part of the proof is the design and analysis of an algorithm that in Lumi allows energy-constrained robots to execute correctly any protocol for robots with unlimited energy. We then show the (apparently counterintuitive) result that in all other models, the energy constraint actually provides the robots with a computational advantage.

• May 31, 13:00—13:40 (MF 3)
  Pieter Voors: The Dynamic Relay Placement Problem: Completing Mesh Networks of Moving Sensors.
  － Abstract
  

  In the relay placement problem, given a set of static sensors and relay range r ≥ 1, we must place a minimum number of static relays such that any two sensors can communicate via the multi-hop wireless sensor network with communication ranges 1 and r for sensors and relays respectively. Allowing sensors to communicate directly or not (1- versus 2-tiered) and providing options for relay placement or not (discrete versus continuous) gives multiple variations. We extend this to the dynamic relay placement problem where sensors move along given paths, requiring full connectivity at any point in time, and explore the implications of this for all combinations of these variations in the 2D Euclidean plane.
  
  All variations are proven to be NP-complete. We show that it is NP-hard to approximate the 1-tiered variants within a constant factor and propose an exponential-time 4-approximation algorithm. We construct approximation schemas for the 2-tiered continuous variant that combine an existing problem with the newly proposed NP-complete line segment unit disc cover problem, for which we create various O(1)-approximation algorithms. For the 2-tiered discrete variant, we create an approximation schema using the existing static variant of it and optimize existing algorithms for it in the process.

• May 31, 11:30—12:15 (MF 6.131)
  Jules Wulms: The Influence of Dimensions on the Complexity of Computing Decision Trees.
  － Abstract
  

  A decision tree recursively splits a feature space $\mathbb{R}^d$ and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work treats heuristic algorithms to compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number $d$ of dimensions of the feature space. We show that it can be solved in $O(n^{2d + 1})$ time, but under reasonable complexity-theoretic assumptions it is not possible to achieve $f(d) \cdot n^{o(d / \log d)}$ running time, where $n$ is the number of training examples. The problem is solvable in $(dR)^{O(dR)} \cdot n^{1+o(1)}$ time, if there are exactly two classes and $R$ is an upper bound on the number of tree leaves labeled with the first class.

• May 30, 10:45—11:25 (MF 14)
  Youri Sio: Hypergraph Crossing Minimization.
  － Abstract
  

  The crossing number is considered a standard quality criterion in (hyper)graph drawings. However, determining the crossing number is NP-hard. Current hypergraph drawing algorithms do not always exploit the subtle differences between the various hypergraph drawing methods. We find that the edge-based drawing method can have a strictly lower crossing number than the incidence representation by reinserting hyperedges as minimum crossing Steiner trees. In addition, we found that hypergraph supports can be optimized for minimum crossings with limited to no effect on the support length. The introduced algorithms are implemented on top of existing software libraries and then evaluated on their performance. Using these algorithms, hypergraph supports can often be drawn with significantly fewer crossings at the cost of a small increase in support length, and edge-based hypergraph drawings can have a lower crossing number than what is possible in the incidence representation.

• May 24, 11:30—12:15 (MF 15)
  Soeren Nickel: Unit Disk Representations of Embedded Trees, Outerplanar and Multi-Legged Graphs.
  － Abstract
  

  A unit disk intersection representation (UDR) of a graph G represents each vertex of G as a unit disk in the plane, such that two disks intersect if and only if their vertices are adjacent in G. A UDR with interior-disjoint disks is called a unit disk contact representation (UDC). We prove that it is NP-hard to decide if an outerplanar graph or an embedded tree admits a UDR. We further provide a linear-time decidable characterization of caterpillar graphs that admit a UDR. Finally we show that, using dynamic programming, it can be decided in linear time if a lobster graph admits a monotone weak UDC, which permits intersections between disks of non-adjacent vertices.

• Mar 21, 13:30—14:10 (MF 2)
  Thomas Derwig: A Kinetic Clustering Using DBSCAN.
  － Abstract
  

  This paper looks into clustering a data set consisting of moving points. Specifically it proposes multiple algorithms to create and more importantly efficiently update a DBSCAN clustering for moving points. That is, to efficiently update the clustering without completely recomputing it when only part of the data changes. For this type of clustering there is no previous research done into maintaining it for moving points, thus this paper gives an initial proposal that sees some success but is also meant to be further built upon. This initial approach is focused on adapting existing algorithms by identifying components that are not necessary to update the clustering for a single point change and pruning these to get a streamlined version that can perform localized cluster update only where an update is needed. Furthermore it explores ways to create an approximate clustering based on various different properties of the updates to the data. These proposed algorithms were tested on a limited but relevant data set. The algorithms proposed in this paper can be used to more efficiently compute consecutive clusterings for any locational data that changes with time such as an analysis of movement trajectories using clustering at different points in time.

• Mar 17, 15:00—15:40 (Zwarte Doos 1.03)
  Jeroen Schols: Kernelization for Treewidth-2 Vertex Deletion.
  － Abstract
  

  The Treewidth-2 Vertex Deletion problem asks whether a set of at most $t$ vertices can be removed from a graph, such that the resulting graph has treewidth at most two. A graph has treewidth at most two if and only if it does not contain a $K_4$ minor. Hence, this problem corresponds to the NP-hard $F$-Minor Cover problem with $F = \{K_4\}$. For any variant of the $F$-Minor Cover problem where $F$ contains a planar graph, it is known that a polynomial kernel exists, i.e., a preprocessing routine that in polynomial time outputs an equivalent instance of size $t^{O(1)}$. However, this proof is non-constructive, meaning that this proof does not yield an explicit bound on the kernel size. The $\{K_4\}$-Minor Cover problem is the simplest variant of the $F$-Minor Cover problem with an unknown kernel size.
  
  To develop a constructive kernelization algorithm, we present a new method to decompose graphs into near-protrusions, such that near-protrusions in this new decomposition can be reduced using elementary reduction rules. Our method extends the ‘approximation and tidying’ framework by van Bevern et al. [Algorithmica 2012] to provide guarantees stronger than those provided by both this framework and a regular protrusion decomposition. Furthermore, we provide extensions of the elementary reduction rules used by the $\{K_4, K_{2,3}\}$-Minor Cover kernelization algorithm introduced by Donkers et al. [IPEC 2021].
  
  Using the new decomposition method and reduction rules, we obtain a kernel consisting of $O(t^{41})$ vertices, which is the first constructive kernel. This kernel is a step towards more concrete kernelization bounds for the $F$-Minor Cover problem where $F$ contains a planar graph, and our decomposition provides a potential direction to achieve these new bounds.

• Mar 08, 10:30—12:00 (MF 3.122 and Zoom)
  Aleksandr Popov, Tom Peters, and Max van Mulken: EuroCG Practice Talks.
  － Abstract
  

  The talks are 12 minutes long in 15-minute slots. We schedule 30 minutes per talk to accommodate questions and feedback.
  1. Aleksandr Popov — Segment Visibility Counting Queries in Polygons
  2. Tom Peters — Fast Reconfiguration for Programmable Matter
  3. Max van Mulken — Kinetic Group Density in 1D

• Jan 31, 11:00—12:00 (MF 3)
  David Dekker: Kernelization for Feedback Vertex Set via Elimination Distance to a Forest.
  － Abstract
  

  We study efficient preprocessing of the Feedback Vertex Set problem, a fundamental problem in graph theory which asks for a minimum vertex set whose removal yields an acyclic graph. More precisely, we aim to determine for which parameterizations this problem admits a polynomial kernel. While a characterization is known for the related Vertex Cover problem, it remained an open problem whether this could be generalized to Feedback Vertex Set. We prove that this problem has a polynomial kernel when parameterized by the deletion distance to a graph of bounded elimination distance to a forest. Furthermore, we prove that no polynomial kernel exists when one uses the deletion distance to a minor-closed graph class that has unbounded elimination distance to a forest as parameterization. We thereby give a characterization of which parameterizations allow a polynomial kernel for this problem, which surprisingly differs from the known characterization of Vertex Cover.