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.

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

• 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.

• Oct 12, 16:00—17:00 (Atlas 0.710 and Teams)
  Aleksandr Popov: Algorithms for Imprecise Trajectories.
• Nov 21, 16:00—17:00 (Atlas 0.710 and Teams)
  Henk Alkema: Geometric TSP and Related Problems in (Almost) Low-Dimensional Spaces.

Past talks

• Jul 20, 15:00—15:40 (MF 3.122)
  Bart van der Steenhoven: Kernelization for Counting Problems on Graphs.
  － Abstract
  

  We focus on the design of polynomial-time preprocessing algorithms for hard counting problems, such that the algorithms have a provable bound on the size of the preprocessed instance. While such algorithms have been extensively studied for decision problems, the research in this direction for counting problems is limited. We present a general technique that can be used for counting problems on graphs to find a polynomial-time algorithm that, given a graph $G$ and an integer $k$, either outputs the number of minimum solutions of size at most $k$, or outputs a $\mathrm{poly}(k)$-size instance that has the same number of such solutions. We apply this technique to the problems of counting minimum feedback vertex sets in undirected graphs and counting minimum dominating sets in planar graphs. These results relate to the notion of kernelization from the study of parameterized complexity, and through our results we present a new model for kernelization for counting problems. This opens the way for further research in this model on such data-reduction algorithms for counting problems.

• Jul 12, 13:00—13:40 (MF 13)
  Bob Krekelberg: Fully Dynamic Maximal Independent Set in Polylogarithmic Update Time.
  － Abstract
  

  The Maximal Independent Set (MIS) problem is a fundamental problem in theoretical computer science and combinatorial optimization, aiming to find a set of mutually non-adjacent vertices in a graph, where no superset of the set is also an independent set. While efficient solutions exist in the classical model of computation, the problem becomes more challenging in the fully dynamic model, where edge updates, both insertions and deletions, are allowed during the algorithm’s execution.
  
  In this thesis, we build upon recent advancements in the field, starting from the breakthrough result presented in STOC’18, which provided the first algorithm for maintaining an MIS faster than computing an MIS from scratch after each edge update. This result triggered a line of research which ended at FOCS’19 with $O(\log^4 n)$ expected update time, where $n$ is the number of vertices in the graph.
  
  In this work, we present a novel randomized dynamic algorithm that improves upon the previous state-of-the-art solutions. Our algorithm achieves an $O(\updateTime)$ amortized expected update time, making it more efficient in maintaining the maximal independent set in a dynamic graph.

• Jul 10, 15:00—15:40 (MF 13)
  Steven van den Broek: Highlighting Patterns in Categorical Point Data Using Simple Shapes.
  － Abstract
  

  We introduce a new approach to visualizing categorical point data. This data can be viewed as a set $S$ of colored points in the plane, where each color represents a category. Our approach identifies patterns formed by points of the same color and highlights them with simple enclosing shapes. Optionally, a visual connection is added between these enclosing shapes by coloring their boundary or connecting the shapes with curves. Because our visualization arises from the partition of colored points into patterns, the focus of this thesis is understanding the algorithmic problems underlying the creation of a good partition. The two patterns we focus on in this thesis are islands—with special attention to a subclass we call dense islands—and reefs. An island $I$ is a subset of $S$ whose convex hull contains no points of $S \setminus I$. A reef is a curve formed by a sequence of points in $S$ that lie close together, with restrictions on the turns it makes. We discuss three greedy algorithms for partitioning points into islands and prove bounds on their approximation ratio. Furthermore, we formulate a dynamic program for finding a reef of maximum cardinality and a heuristic for finding a large dense island.
  
  Our visualization of real-world data sets from the literature has low visual complexity compared to state-of-the-art visualizations. Moreover, the partitions underlying the visualization are of good quality and can be readily generated in reasonable time. This is in contrast to our theoretical analysis, which indicates that the worst-case performance of the algorithms used in our visualization for arbitrary inputs is poor. An interesting direction for future work is to define realistic inputs and analyze the performance of our algorithms in that setting.

• Jul 05, 16:00—16:40 (MF 11)
  Vincent Moonen: Bottlenecks in Programmable Matter.
  － Abstract
  

  A desired function of programmable matter is shape formation. The reconfiguration algorithm by Kostitsyna, Peters, and Speckmann achieves this by routing particles through the configuration of matter. The efficiency of this can be limited when the internal supply graph which routes the particles, contains overlapping shortest paths. We explore the properties of these supply graphs and their novel shortest paths to arrive at sound definitions for bottlenecks in these graphs, and we explore ways of detecting such limitations in the throughput of particles through the supply graphs.

• Jul 05, 14:00—14:40 (MF 6.131)
  Maxim Snoep: Polycube Construction via Iterative Loop Selection.
  － Abstract
  

  Polycubes are an important intermediate step for various problems in computer graphics and computational modeling, such as hex-mesh construction, seamless texture mapping, spline fitting, and multi-block grid generation. The construction of polycubes and a minimal distorting parameterization between an input triangle mesh and a polycube is a complex problem. State-of-the-art polycube construction algorithms fail to address robustness issues adequately. We present a robust pipeline for computing polycube layouts based on iterative refinement by approaching the polycube construction problem with a characterization of polycubes in the dual setting. The pipeline has been implemented and demonstrated on various benchmark models. The approach has a stronger theoretical foundation than current polycube construction, furthermore, the high modularity of the pipeline results in the potential for many future improvements.

• Jul 04, 16:00—17:00 (Atlas 0.710 and Teams)
  Jari de Kroon: Parameterized Graph Modification Beyond the Natural Parameter.
• Jun 28, 10:30—11:10 (MF 3.119)
  Wessel van Lierop: Co-clustering in Uncertain-Data Applications of DBSCAN.
  － Abstract
  

  In the context of clustering algorithms for uncertain data, interesting problems related to the inherent probabilistic aspect of such data can arise. For variants of the DBSCAN clustering algorithm, this thesis addresses the probability that two arbitrarily chosen points will be assigned to the same cluster, or co-clustered. Existing algorithms avoid computing these values directly, opting instead for clustering methods whose outputs do not necessarily correspond to probabilities. In this work, the task of finding this co-clustering probability is framed as a graph connectivity problem. Within this setting, a particular graph structure is analyzed that, if detected within a dataset, guarantees a lower bound on the probability value of interest. Approximate solutions to the co-clustering problem can be relevant with regard to data analysis, and the theoretical framework laid out could prove useful in the context of other uncertain-data reachability problems.

• Jun 05, 10:00—10:40 (MF 3.070)
  Vasil Sirakov: CURE Clustering: Analysis and Parallelization.
  － Abstract
  

  Clustering is a widely-used technique for extracting features and finding patterns from an input set of data points by placing them into groups based on how similar they are to each other.
  
  This thesis explores a type of clustering called Agglomerative Clustering (AC) and more specifically, a variant called single-link. In this variant, every data point starts in a separate cluster and at each iteration, the two clusters with the shortest distance between a pair of each other’s points are merged together. The focal point of this study is the CURE (CLustering Using Representatives) algorithm. Despite being an agglomerative clustering algorithm, CURE sets itself apart by introducing some novel concepts. It uses only a constant number of points called representatives from each cluster when determining which ones to merge. Furthermore, those representatives are not static as they can be applied shrinkage (displaced) towards the cluster mean by some factor.
  
  What sets CURE apart is that it accepts both the number of representatives and the level of displacement (shrinkage) applied to them are input parameters. This makes CURE much more versatile than the default Agglomerative Clustering algorithm in different kinds of situations. To properly utilize this flexibility, however, selecting the appropriate input parameters is crucial. Therefore, an analysis of CURE’s behavior is carried out for datasets of various shapes and sizes. The performance and suitability of CURE are evaluated for each dataset variant and the different values of CURE’s input parameters.
  
  By default, CURE operates on a single machine. Its time complexity relative to the dataset size makes it unsuitable for processing large datasets by itself. For this reason, this study takes a look at the possibility of parallelizing the computation of CURE by distributing it onto multiple machines.
  
  We also propose an algorithm for parallelizing CURE called MPC-CURE. It is an adaptation of an existing parallel agglomerative clustering algorithm called Affinity Clustering. MPC-CURE maintains equivalent space, time, and iteration constraint guarantees with Affinity Clustering. Pseudocode is provided to demonstrate how MPC-CURE can be implemented. Additionally, experiments over both synthetic and real-world data are carried out to exhibit the clustering performance and limitations of the parallel algorithm.

• Jun 02, 12:45—13:30 (MF 12)
  Céline Swennenhuis: A Subexponential-Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints.
  － Abstract
  

  In a classical scheduling problem, we are given a set of $n$ jobs of unit length along with precedence constraints, and the goal is to find a schedule of these jobs on $m$ identical machines that minimizes the makespan. Using the standard $3$-field notation, it is known as $\text{Pm}\vert\text{prec}, p_j = 1\vert C_{\max}$. Settling the complexity of $\text{Pm}\vert\text{prec}, p_j = 1\vert C_{\max}$ even for $m = 3$ machines is, together with Subgraph Isomorphism, among the last two open problems from the book of Garey and Johnson [GJ79] for which the computational complexity remains a mystery. We present an algorithm for this problem that runs in $(1 + \frac{n}{m})^{O(\sqrt{nm})}$ time. This algorithm is subexponential when $m = o(n)$.

• May 24, 11:30—12:00 (MF 11)
  Subhash Suri: Obstacle Avoidance.
  － Abstract
  

  Obstacle-avoiding paths are widely studied in computational geometry and graph algorithms as design tools for various applications such as robotics and sensor networks, among others. This talk describes recent progress on obstacle-avoidance problems of the following form: what is the minimum number of obstacles we must remove to reach target point $t$ from start point $s$, or what is the maximum number of obstacles we can remove while blocking all $s–t$ paths. More generally, how many obstacles should be removed to simultaneously reach many $s–t$ pairs. Under some conditions, we can also compute the shortest-length path when at most $k$ obstacles can be removed.

• May 23, 13:00—13:10 (MF 6.131)
  Tristan Trouwen: Algorithms to Interpret Figured Bass Notation.
  － Abstract
  

  This is a presentation on the results of the preparation phase for a graduation project.

• May 22, 13:00—13:40 (MF 3)
  Teun van Zon: Exact and Heuristic Algorithms for a Sequencing Problem of Integer Pairs.
  － Abstract
  

  Producing circuit boards requires machines to pick up and place electric components, also known as the pick-and-place process. Determining an optimal order to pick and place these components can greatly increase the throughput of these machines. This optimization problem consists of multiple subproblems, one of which is determining the optimal locations for the components to be picked up from. This subproblem is called the “Gang-Pick” problem by a Dutch company. In this problem, a profit function is optimized over a set of integer pairs. A chain of reductions from the Numerical Matching with Target Sums problem shows that the Gang-Pick problem is NP-hard. This proof motivates the search for parameterized and approximation algorithms. Two exact algorithms have been developed, a dynamic and an integer linear program. The dynamic program can find an optimal solution in single exponential time to the number of integer pairs. The dynamic program also yields a parameterized, slice-wice polynomial algorithm, with the parameter denoting the number of distinct integer pairs in the input. Furthermore, a new approximation algorithm is proposed, which, tested against real inputs provided by the company, is shown to outperform the currently used heuristic and can find an optimal solution for most inputs. These results could potentially improve the throughput of the pick-and-place process.

• May 01, 10:30—11:10 (MF 4)
  Wietske Blijenberg: Embedding Paths with Directional Constraints on a Grid.
  － Abstract
  

  TBA

• Mar 20, 11:30—12:00 (MF 14)
  Boris Aronov: Dynamic Approximate Multiplicatively-Weighted Nearest Neighbors.
  － Abstract
  

  We describe a dynamic data structure for approximate nearest neighbor (ANN) queries with respect to multiplicatively weighted distances with additive offsets. Queries take polylogarithmic time, while the cost of updates is amortized polylogarithmic. The data structure requires near-linear space and construction time. The approach works not only for the Euclidean norm, but for other norms in $ℝ^d$, for any fixed $d$. We employ our ANN data structure to construct a faster dynamic structure for approximate SINR queries, ensuring polylogarithmic query and polylogarithmic amortized update for the case of non-uniform power transmitters, thus closing a gap in previous state of the art. To obtain the latter result, we needed a data structure for dynamic approximate halfplane range counting in the plane. Since we could not find such a data structure in the literature, we also show how to dynamize one of the known static data structures.

• Mar 15, 14:30—17:00 (MF 15)
  Aleksandr Popov, Thijs van der Horst, Max van Mulken, Bart van der Steenhoven, and Leonidas Theocharous: 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 — Map Matching Queries Under Fréchet Distance on Low-Density Spanners
  2. Thijs van der Horst — Computing Minimum Complexity 1D Curve Simplifications Under the Fréchet Distance
  3. Max van Mulken — Density Approximation for Kinetic Groups
  4. Bart van der Steenhoven — Simply Realising an Imprecise Polyline is NP-hard
  5. Leonidas Theocharous — Clustering with Obstacles

• Mar 02, 14:30—15:10 (Zoom)
  Maas van Apeldoorn: Bridging the Gap: UFO Tree Reconstruction from Incomplete Point Clouds.
  － Abstract
  

  TBA

• Feb 28, 12:00—12:10 (MF 11)
  Damian Buzink: The Effect of Area Preservation on Polygon Simplification.
  － Abstract
  

  This is a presentation on the results of the preparation phase for a graduation project.

• Feb 27, 10:00—10:40 (MF 11)
  Tom van Roozendaal: Fixed-Parameter Tractable Algorithms for Refined Parameterizations of Graph Problems.
  － Abstract
  

  This work contributes as a study on the parameterized complexity of established graph problems using novel parameter candidates. We look at FPT algorithms for solving Triangle Graph Packing, 4-Cycle Graph Packing and Steiner Tree, using refined parameters. These parameters are considered to be refined as they can become much smaller than the solution size, which is considered to be a standard parameter choice. We find $2^{O(d)} · n^{O(1)}$ and $2^{O(d \log d)} · n$ time algorithms for Triangle Graph Packing and 4-Cycle Graph Packing respectively, provided with some $H$-elimination forest of the input graph $G$, with depth $d$, where $H$ denotes the class of triangle or 4-cycle free graphs. We introduce a $2^{O(\lvert S\rvert \log \lvert S\rvert)} · n^{O(1)}$ time algorithm for Steiner Tree when given a multi-way cut $S$ of the input graph $G$. These algorithms solve their perspective problem efficiently on a large range of inputs. To achieve our results, we use known FPT approaches based on solution size to solve subproblem instances in which their solution size is limited by the refined parameter. The results found in this paper can be used generalize an algorithm for Graph Packing and to further investigate the impact of refined parameters on such graph problems.

• Feb 23, 14:30—15:10 (MF 13)
  Arne Gerits: Towards Minimum Distortion Embeddings of Oil Glands in the Rinds of Citrus Fruits.
  － Abstract
  

  TBA

• Jan 31, 14:00—14:40 (MF 14)
  Ying Lu: Distributed Algorithms for Connected Dominating Set on Unit-Disk Graphs.
  － Abstract
  

  In this thesis, we study the design of distributed algorithms for finding a minimum connected dominating set on unit-disk graphs. We first revise a bound from an earlier paper and point out the consequences in follow-up works. Then we describe and improve the location-aware algorithm from Jallu, Prasad and Das and reach an output size of 96 OPT + 48, where OPT is the size of a minimum connected dominating set on the graph. The algorithm takes O(1) rounds of communication and has a message complexity of O(n), where n is the number of nodes in the graph. Finally, we explore the problem in the presence of obstacles. Let V be the node set and O be the obstacle set. Define a block unit-disk graph G(V, O) as a graph where edge (u, v) exists if and only if edge (u, v) exists in the unit-disk graph G(V) and no obstacles from O intersect the line segment connecting node u and node v. We observe that if the obstacles can be arbitrarily small, the problem is as hard as finding a minimum connected dominating set on a general graph. For square obstacles whose side lengths are at least 1, we present an algorithm that finds a connected dominating set on a blocked unit-disk graph G(V, O) with a size of at most min(7752 OPT + 456, 912 OPT + 456 + 114 |O|), where OPT is the size of a minimum connected dominating set on the graph. The time complexity is O(1) and the message complexity is O(n), where n = |V| is the number of nodes in the graph.

• Jan 30, 13:00—13:10 (MF 6.131)
  Bart van Steenhoven: Kernelization for Counting Problems.
  － Abstract
  

  This is a presentation on the results of the preparation phase for a graduation project.

• Jan 26, 14:30—14:40 (MF 11)
  Steven van den Broek: Islands and Bridges: Point-Set Visualization with Convex Shapes.
  － Abstract
  

  This is a presentation on the results of the preparation phase for a graduation project.

• Jan 17, 12:00—12:40 (MF 4)
  Thijs van der Horst: A Subquadratic $n^ε$-Approximation for the Continuous Fréchet Distance.
  － Abstract
  

  The talk is 17 minutes, the rest is scheduled for questions and feedback.
  
  The Fréchet distance is a commonly used similarity measure between curves. It is known how to compute the continuous Fréchet distance between two polylines with $m$ and $n$ vertices in $\mathbb{R}^d$ in $O(mn (\log \log n)²)$ time; doing so in strongly subquadratic time is a longstanding open problem. Recent conditional lower bounds suggest that it is unlikely that a strongly subquadratic algorithm exists. Moreover, it is unlikely that we can approximate the Fréchet distance to within a factor 3 in strongly subquadratic time, even if $d = 1$. The best current results establish a tradeoff between approximation quality and running time. Specifically, Colombe and Fox (SoCG, 2021) give an $O(α)$-approximate algorithm that runs in $O((n³ / α²) \log n)$ time for any $α \in [\sqrt{n}, n]$, assuming $m ≤ n$. In this paper, we improve this result with an $O(α)$-approximate algorithm that runs in $O((n + mn / α) \log³ n)$ time for any $α \in [1, n]$, assuming $m ≤ n$ and constant dimension $d$.

• Jan 17, 10:30—11:30 (MF 4)
  Celine Swennenhuis: Research Talk and Mini-Lecture.
  － Abstract
  

  This is a talk by a potential new hire, see slack for details. Send any feedback to Mark de Berg.

• Jan 16, 10:30—11:30 (MF 3)
  Roohani Sharma: Research Talk and Mini-Lecture.
  － Abstract
  

  This is a talk by a potential new hire, see slack for details. Send any feedback to Mark de Berg.

• Jan 13, 16:00—16:10 (MF 13)
  Job van Dooren: Kinetic Data Structures for Geometric Matchings.
  － Abstract
  

  This is a presentation on the results of the preparation phase for a graduation project.

• Jan 10, 10:30—11:30 (MF 4)
  Thekla Hamm: Research Talk and Mini-Lecture.
  － Abstract
  

  This is a talk by a potential new hire, see slack for details. Send any feedback to Mark de Berg.

• Jan 09, 13:30—14:30 (MF 6.131)
  Ioana Bercea: Research Talk and Mini-Lecture.
  － Abstract
  

  This is a talk by a potential new hire, see slack for details. Send any feedback to Mark de Berg.