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 2024. 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 thijs to schedule your talk. No talks are planned at the moment.

Past talks

• Sep 11, 15:00—15:45 (MetaForum 3.119)
  Steven van den Broek: COSIT Practice Talk.
  － Abstract
  

  This is a session for practicing COSIT presentations.
  Presentations are 15 minutes, after which there is room for questions and feedback.
  There is one talk in this session:
  
  Steven van den Broek: Scalable Harmonious Simplification of Isolines

• Aug 28, 15:00—15:45 (MetaForum 3.119)
  Ruben Verhaegh: IPEC Practice Talk.
  － Abstract
  

  This is a session for practicing IPEC presentations.
  There is one talk in this session:
  
  Ruben Verhaegh: Preprocessing to Reduce the Search Space for Odd Cycle Transversal

• Jul 18, 13:30—15:30 (MetaForum 13)
  Faezeh Motiei: Parameterized Algorithms for Enumerating Sparse Secluded Subgraphs, with Applications to Scattered Graph Classes.
  － Abstract
  

  We explore the concept of k-secluded subgraphs, defining a k-secluded subgraph as one whose open neighborhood contains at most k vertices. Our analysis focuses on fixed-parameter tractable (FPT) algorithms for identifying k-secluded subgraphs that have a structure close to trees. Specifically, these subgraphs become trees after the removal of a fixed number of edges or vertices. We present algorithms for the weighted version of this problem, aiming to identify all maximum weight k-secluded subgraphs within the mentioned graph classes. These algorithms build on the approach by Jansen et al. for finding all maximum weight k-secluded trees, leveraging a recursive branching strategy on the final status of specific vertices in the target subgraphs.
  
  Additionally, we investigate an application of this problem known as Deletion to Scattered Graph Classes. Here, the objective is to simplify the graph by deleting up to k vertices so that each connected component in the remaining graph belongs to a specified graph class. An FPT algorithm exists for cases where graph classes are characterized by forbidding a finite set of induced subgraphs. However, trees and graph classes with structures similar to trees cannot be characterized by a finite set of forbidden patterns. In this thesis, we utilize algorithms for finding specific sets of k-secluded subgraphs as a subroutine to tackle particular instances of the Deletion to Scattered Graph Classes problem, noting that each connected component of the remaining graph is a k-secluded subgraph of the original graph within its respective graph class.

• Jul 17, 10:00—10:30 (MetaForum 13)
  Vincent Janssen: Thermal-aware Task Scheduling for 3D Multi-Processors.
  － Abstract
  

  This thesis looks at the efficient scheduling of tasks on 3D multi-processors. 3D multi-processors work best when they stay below a certain temperature threshold. This thesis focuses on problem formulations and thermal models to schedule tasks while staying under a threshold temperature. Most research concerning this topic focuses on empirical approaches, whereas this thesis focuses on analytical approaches to solving this scheduling problem. The initial approach focused on taking a model from existing research, proving analytical properties, and finding special cases that can be computed efficiently. Novel models are presented based on this initial problem. For each problem formulation, analytical results, such as special cases that are efficiently solvable and hardness results, and approximation algorithms are presented. The performance of the models is demonstrated using experiments on randomly generated datasets using a thermal simulator. This thesis introduces analytical frameworks and approximation algorithms for the efficient scheduling of tasks on 3D multi-processors with temperature constraints, providing a theoretical alternative to existing empirical methods, together with numerous open problems for further research.

• Jul 15, 13:00—13:30 (MetaForum 13)
  Jeroen Lamme: Fixed-Parameter Tractable Algorithms for Rejection-Proof Kidney Exchange.
  － Abstract
  

  Kidney exchange programs (KEPs) facilitate the exchange of kidneys for living organ donation by finding transplantation cycles and chains containing multiple patient-donor pairs. By combining different KEPs belonging to different agents into a multi-agent kidney exchange program (mKEP), more transplantations can be performed. This requires balancing between agents’ incentives and optimizing the number of transplantations in the mKEP. One possible approach is to make rejection-proof transplantation plans. Given an mKEP, the rejection-proof kidney exchange problem asks if there exists a collection of transplantation cycles and chains where no agent benefits from rejecting proposed cycles or chains and replacing them with their own. Blom, Smeulders, and Spieksma [4] show that this problem is Σ_2^p-complete, and thus it is not expected that polynomial time algorithms exist that solve it. We provide the first fixed-parameter tractable (FPT) algorithms for solving this problem. We present a kernel for both a graph and a set representation of mKEPs. We apply techniques used for regular KEPs and the sunflower lemma, respectively, for creating these kernels. The parameter choices for the rejection-proof kidney exchange problem used in this thesis include; the number of helped patients + the size of sets, the size of a hitting set of the family of sets containing sets representing cycles and chains + the size of sets, and the value of helped patients + the maximum degree of the graph modeling the mKEP + the maximum chain and cycle length. Our results allow for a better theoretical understanding of rejection-proofness and open the door for further development of FPT algorithms for rejection proof kidney exchange.

• Jul 12, 10:30—11:00 (MetaForum 4)
  Michel van de Looij: Dynamic Path Planning on 3D Surfaces.
  － Abstract
  

  This thesis discusses a path planning problem with a target that walks on the floor of a 3D environment while a chaser is allowed to climb on any surface in that environment. Various methods of generating a probabilistic roadmap to approximate this environment and several path planning algorithms can be used to accomplish this, but which combination of algorithms leads to efficient and natural looking paths? While much research has gone into this problem in a 2D setting or a 3D setting where both agents walk on the floor or fly through the environment, the 3D setting where an agent is allowed to climb on all surfaces brings several challenges that have been overlooked due to the niche use cases of this problem. We will introduce several methods of generating a probabilistic roadmap which utilise standard approaches as well as approaches that take advantage of the 3D environment, in addition to introducing standard approaches for planning a path in the 3D environment where the target also moves around the environment. These probabilistic roadmap generation methods have been tested and taking advantage of the 3D environment had a positive impact on their performance, which in turn resulted in more natural paths for the path planning algorithms, which have also been tested and showed that multiple approaches are feasible depending on the priorities of the use case. These results are a solid foundation for solving the problem of dynamic path planning on 3D surfaces, which can then be optimised to encourage the use of it in for example games and rescue operations.

• Jul 10, 11:00—11:30 (MetaForum 15)
  Daan Boelhouwers: On the Stability of Kinetic Euclidean Matching.
  － Abstract
  

  The Euclidean matching problem finds practical applications in many areas, among which wireless networks, where it can be used to model the optimal pairing of network devices. Nowadays, many of the devices connected to a network move around. Examples of such devices include portable devices such as phones, but also many vehicles such as cars, airplanes, and drones, which are increasingly often connected to a network. Motivated by this, we define two different kinetic variants of the problem, which we name kinetic matching and fading matching. For both of these variants, it could be that the optimal solution changes frequently as the points move around, in which case the optimal solution is unstable. In many practical applications, it is often desirable that a maintained solution is stable. However, since the optimal solution is unstable, enforcing stability will inevitably lead to a reduction in the quality of the maintained solution. We investigate this trade-off between stability and solution quality by studying the topological stabilityof the problem. Topological stability allows a solution to change arbitrarily fast, as long as it does so continuously. For both kinetic and fading matching, we derive bounds on the topological stability ratio, which is the best achievable approximation ratio of any topological stable algorithm, under various constraints.

• Jul 09, 13:00—13:30 (MetaForum 15)
  Jarl Jansen: Minimum-Cost Perfect Matching on Regions in the Plane.
  － Abstract
  

  Let ???? be a set of 2???? regions in the plane, where the edge connecting regions ????_????, ????_???? ∈ ???? has a weight equal to the Euclidean distance ????(????_????, ????_???? ) between regions ????_???? and ????_???? . In the region-matching problem, the goal is to compute a subset ???? of edges, where |????| = ???? such that every region is incident to one edge from ????, and Σ(????????,???????? )∈???? ????(????????, ???????? ) is minimized. The region-matching problem can be solved using general-graph matching algorithms in ????(????^3) time. Vaidya [28] and Varadarajan [29] show that for points in the plane, the geometry can be exploited to solve the matching problem in sub-cubic time. We generalize the techniques by Varadarajan and Vaidya to obtain sub-cubic algorithms for a various classes of regions.

• Jul 08, 14:00—14:30 (MetaForum 15)
  Maik Dijkstra: Shortest Path Problems on Indecisive Graphs.
  － Abstract
  

  In this thesis, we explore the computational complexity of several shortest path problems on indecisive graphs. An indecisive graph is a graph where the vertices correspond to points with multiple possible coordinates. In a realisation of this graph, every point is realised on exactly one of its coordinates and the edge weights are defined by the Euclidean distance between the endpoints of the edge. Previous research on uncertainty in the shortest path problem focuses on uncertainty in the edge weights between points while this thesis focuses on the uncertainty in the coordinates of points. The uncertainty in the coordinates of the points results in dependencies between the coordinates of a point and the edge weight. We provide a polynomial time algorithm for computing the shortest shortest path from a single source ???? to a single target ???? and between all pairs of source and target on an indecisive graph. Furthermore, we show that computing the longest shortest path from ???? to ???? is NP-Hard. Next to this, we provide several conditions for which the longest shortest path is polynomial time computable and several constraints on the indecisive graphs such that computing the longest shortest path remains NP-Hard. At last, we show that computing the expected length of the shortest path is #P-Hard. Together, these results form the first bridge between the well-known shortest path problem and indecisive graphs.

• Jul 01, 14:00—14:30 (MetaForum 15)
  Jeroen Hellenbrand: Weight Estimation of Beef Tomatoes using Partial Point Clouds.
  － Abstract
  

  In this thesis, we explore weight estimation of 3D objects using point cloud data, specifically targeting beef tomatoes. The primary objective of this thesis is to develop an efficient and accurate algorithm capable of estimating the weight of these tomatoes by reconstructing their surfaces from partial point clouds. Previous work has failed to address all the steps required for accurate volume and weight estimation of 3D objects from partial point clouds. To address this gap, we propose a novel algorithmic technique composed of several sub-algorithms for preprocessing and completing point clouds, reconstructing surfaces, and estimating the tomatoes’ weight. We evaluate the performance of our algorithm through experiments on datasets containing partial point clouds of weighed beef tomatoes. The results demonstrate the practical potential of our algorithm, providing accurate weight estimations and valuable insights into the tomatoes’ shape, position, and orientation through the reconstructed surfaces.

• Jun 07, 15:00—17:00 (MetaForum 3.119)
  : SWAT Practice Talks.
  － Abstract
  

  This is a session for practicing SWAT presentations.
  There are two talks in this session:
  
  Tom Peters: Optimal in-Place Compaction of Sliding Cubes
  Ruben Verhaegh: Search-Space Reduction via Essential Vertices Revisited: Vertex Multicut and Cograph Deletion

• Jun 04, 11:15—12:00 (MetaForum 14)
  Liana Khazaliya: Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover.
  － Abstract
  

  Treewidth is an important parameter that, when bounded, yields tractability for many problems. For example, graph problems expressible in the language of Monadic Second Order logic are fixed-parameter tractable parameterized by the treewidth of the input's (primal) graph plus the length of the MSO-formula. While this celebrated result readily gives algorithms for numerous problems, the running time is notoriously bad as the function of treewidth is an exponential tower whose height is linear in the length of the formula. As this bound is likely to be much higher than optimal, a lot of effort has been put on providing tighter bounds on the dependency on the treewidth. For the majority of problems, it has been shown that this dependency is single-exponential, that is, of the form 2^{O(tw)}. In fact, very few problems are known to have a worse dependency and no problems in NP were known to even have a double-exponential dependency. In this talk, we present a novel, yet simple versatile technique based on Sperner families to show that a double-exponential dependency on the treewidth (and even the vertex cover) is required for some problems in NP.
  
  This is a joint work with F. Foucaud, E. Galby, S. Li, F. Mc Inerney, R. Sharma, P. Tale, accepted to ICALP 2024
  ArXiv: 2307.08149v4

• Apr 04, 12:30—13:00 (MetaForum 3)
  Lotte van Gessel: Sorting Tomatoes into Bins with Weight and Cardinality Constraints.
  － Abstract
  

  In this thesis, we investigate the fixed-count sorting problem that focuses on a machine sorting certain
  products that enter in a partially online manner into bins while maintaining several requirements. The goal of this thesis is to create an algorithm for the operation of the machine which results in a low percentage of underweight bins, low average giveaway weight, high efficiency, and a certain uniformity of products within the bin. We develop new algorithms for three aspects of this problem. Two algorithms for optimizing the setup of the machine and one algorithm to optimize the machine’s performance when it is in operation. Together, these algorithms cover all crucial tasks within the machine. We present the results of our algorithms obtained via extensive simulations for various combinations of relevant parameters of our algorithms. The described algorithms meet the requirements for percentage underweight bins, giveaway weight, efficiency, and uniformity as set by the problem.

• Mar 19, 15:00—16:00 (MetaForum 6.131)
  Tristan Trouwen: Improved Automatic Realization of Figured Bass.
  － Abstract
  

  Figured bass is a notation method to describe the accompaniment of baroque music. However, it is hard to read for many amateur players due to the plethora of rules, and required improvisation. This thesis addresses this challenge of realizing figured bass, by building upon earlier work. Although previous research exists, it has significant limitations, particularly due to its numerous assumptions, its treatment of passing notes, and lack of ornamentation. The overarching objective is to enhance flexibility and quality in figured bass realization, catering to the varied requirements of different continuo players. In this thesis, we model several musical aspects in terms of numeric cost functions,
  allowing us to advance earlier work by allowing multiple voicings, key-changes, passing notes, and ornamentations. In several experiments, we showcase the quality and flexibility of our approach, while receiving positive feedback from an expert. The presented method can help amateur players and can serve as a robust starting point for further refinement in the field of figured bass realization.

• Mar 05, 15:00—17:05 (MetaForum 3.122)
  : EuroCG and LATIN Practice Talks Session 2.
  － Abstract
  

  This is the second session for practicing EuroCG and LATIN presentations.
  Presentations for EuroCG are 12 minutes long and given a slot of 25 minutes.
  Presentations for LATIN are 20 minutes long and given a slot of 35 minutes.
  The schedule for this session as follows:
  
  15:00-15:25 Steven van den Broek: Greedy Monochromatic Island Partitions
  15:25-15:50 Anna Schenfisch: Lower Bounding Minimal Faithful Sets of Verbose Persistence Diagrams
  15:50-16:15 Tom Peters: Optimal In-Place Compaction of Sliding Cubes
  16:15-16:40 Soeren Terziadis: On Orbital Labeling with Circular Contours
  16:40-17:05 Leonidas Theocharous: A Clique-Based Separator for Intersection Graphs of Geodesic Disks in R^2

• Feb 27, 15:00—16:50 (MetaForum 11/12)
  : EuroCG and LATIN Practice Talks Session 1.
  － Abstract
  

  This is the first session for practicing EuroCG and LATIN presentations.
  Presentations for EuroCG are 12 minutes long and given a slot of 25 minutes.
  Presentations for LATIN are 20 minutes long and given a slot of 35 minutes.
  The schedule for this session as follows:
  
  15:00-15:35 Nathan van Beusekom: Competitive Searching over Terrains
  15:35-16:00 Thijs Beurskens: An Interleaving Distance for Ordered Merge Trees
  16:00-16:25 Max van Mulken: Capturing the Shape of a Point Set with a Line-Segment
  16:25-16:50 Arjen Simons: Hausdorff Morphs with Fewer Components

• Feb 20, 10:30—11:00 (MetaForum 4.208)
  Tobias van Elk: Estimating Contours Using Uncoordinated Mobile Sensors.
  － Abstract
  

  Wireless sensor networks (WSN) have seen increasing adoption for many different applications and problem domains. A WSN consists of a number of sensor nodes, sometimes referred to as motes, which are connected wirelessly to form a network. Each node measures some physical attribute of its environment and communicates it to a base station by transmitting the data via the other sensor nodes on the network.
  We are interested in creating an online algorithm that takes the measurements reported by some WSN to generate an animated contour plot. In other words, we are interested in the development of the contour over time. These measurements evolve over time, thus the algorithm must continuously adapt the animation as new values are reported. In this talk, we discuss relevant, existing literature, present our formal problem statement and our proposed solution and a discussion of its performance.

• Feb 19, 12:30—13:00 (MetaForum 15)
  Denis Shehu: An Analysis of the Effect of Polysemy on the Topology of the Latent Manifoldan.
  － Abstract
  

  A static word embedding is a ????-dimensional vector representation of a word, learned by a machine learning model trained on the occurrences of this word in a text corpus. If the word is a polyseme, i.e. its occurrences in the corpus have different meanings, then its static embedding must represent all these meanings. To achieve this, it has been hypothesized that the region around the embedding must be a singularity. Previous work has used topology-based algorithms for singularity identification to a very limited extent to provide evidence for this hypothesis. We apply three such algorithms to the embeddings of a carefully constructed list
  of polysemes and monosemes, i.e. words that have a single meaning (the region around them is hypothesized to not be a singularity). We distinguish two types of polysemes, namely: interclass polysemes, which occur in the corpus as nouns and verbs, and intraclass polysemes, which occur as either nouns or verbs. Before applying the algorithms to the embeddings, we identify and fix some of their shortcomings and evaluate their efficacy on synthetic datasets. This evaluation process aids us to better understand the results of applying the algorithms to the embeddings, results which might suggest that interclass and intraclass polysemes are much more different than expected.

• Feb 16, 16:00—17:00 (Atlas 0.710 and Teams)
  Pantea Haghighatkhah: Exploring the Geometry of Semantic Spaces.
• Feb 13, 11:15—12:00 (MetaForum 6.131)
  Markus Utke: Towards Characterizing Truthful Mechanisms for Budget Aggregation.
  － Abstract
  

  In the budget aggregation problem we try to unify different preferences on how to distribute a divisible resource over a number of alternatives. We study mechanisms that are truthful, i.e. do not incentivize agents to lie about their preferences. We try to characterize the sets of mechanisms that satisfy truthfulness in combination with additional desirable properties.

• Feb 08, 13:30—14:00 (MetaForum 1.130)
  Faezeh Motie: Preperation Phase Defense.
  － Abstract
  

  Faezeh Motie - FPT Algorithms for Finding and Enumerating k-Secluded Subgraphs

• Feb 05, 13:00—13:30 (MetaForum 3.141)
  Jeroen Lamme: Preperation Phase Defense.
  － Abstract
  

  Jeroen Lamme - FPT Algorithms for Multi-Party Kidney Exchange

• Jan 29, 09:30—10:30 (MetaForum 15)
  Vincent Janssen and Maik Dijkstra: Preperation Phase Defenses.
  － Abstract
  

  Vincent Janssen - Thermal-aware Task Scheduling for 3D Multi-Processors
  Maik Dijkstra - Shortest Paths with Uncertain Node Positions

• Jan 24, 11:15—12:00 (MetaForum 14)
  Soeren Terziadis: Minimum Link Fencing (A Geometric Approach to a Bovine Problem).
  － Abstract
  

  We study a variant of the geometric multicut problem, where we are given a set $P$ of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where $P$ contains a polygon $Q$ that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general, however, it is polynomial-time solvable when each fence contains at most two polygons and is composed of a bounded number of segments, as well as when the convex hull of $P$\$Q$ does not intersect $Q$.