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 2023. Schedules are available between 2005 and 2023.

• 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. No talks are planned at the moment.

Past talks

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