SIGalgo Symposium

The third SIGalgo.nl symposium will take place on October 21st, 2026 in Amsterdam.

Date:

October 21st, 2026

Place:

All events will take place at Vrije Universiteit NU Building (De Boelelaan 1111, 1081 HV Amsterdam) on 2nd, 4th or main floor:

• Talks: Theater 8
• Coffee breaks and Lunch: Lobby Campus Square on the 2nd floor
• Drinks: Grand Cafe LIVING, Main Floor

Directions: 

Arriving by train from Amsterdam Zuid, you can leave the platform towards Parnassusweg direction and walk for less than 10 minutes. The walk is slightly longer if you exit from the station hall (e.g. arriving by metro). 

Registration:

Please register here.

Program: 

Abstracts:

Improved Space-Time Tradeoffs for Permutation Problems via Extremal Combinatorics (Shengzhe Wang): We provide improved space-time tradeoffs for permutation problems over additively idempotent semi-rings. In particular, there is an algorithm for the Traveling Salesperson Problem that solves N-vertex instances using space S and time T where S⋅T≤3.1861^N. This improves a previous work by Koivisto and Parviainen [SODA'10] where S⋅T≤3.9271^N, and overcomes a barrier they identified, as their bound was shown to be optimal within their framework.
To get our results, we introduce a new parameter of a set system that we call the chain efficiency. This relates the number of maximal chains contained in the set system with the cardinality of the system. We show that set systems of high efficiency imply efficient space-time tradeoffs for permutation problems, and give constructions of set systems with high chain efficiency, disproving a conjecture by Johnson, Leader and Russel [Comb. Probab. Comput.'15].

Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain (Frank Staals): We present efficient data structures for approximate nearest neighbor searching and approximate 2-point shortest path queries in a two-dimensional polygonal domain P with n vertices. Our goal is to store a dynamic set of m point sites S in P so that we can efficiently find a site s∈S closest to an arbitrary query point q. We will allow both insertions and deletions in the set of sites S. However, as even just computing the distance between an arbitrary pair of points q,s∈P requires a substantial amount of space, we allow for approximating the distances. Given a parameter ε>0, we build an O((n/ε)log n) space data structure that can compute a 1+ε-approximation of the distance between q and s in O(1/ε^2)log n) time. Building on this, we then obtain an O((n+m)/ε)log n+(m/ε)log m) space data structure that allows us to report a site s∈S so that the distance between query point q and s is at most (1+ε)-times the distance between q and its true nearest neighbor in O((1/ε^2)log n+(1/ε)log n log m +(1/ε)log^2 m) time. Our data structure supports updates in O((1/ε^2)log n+(1/ε)log n log m+ (1/ε)log^2m) amortized time.

Single-Source Shortest Paths in Pseudodisk Graphs (Mark de Berg): We study Single-Source Shortest Paths (SSSP) on unweighted intersection graphs whose node set corresponds to a set of n constant-complexity objects in the plane. We prove SSSP can be solved in O(U(n) polylog n) expected time for any class of objects whose union complexity is U(n). This given O(n polylog n)  SSSP algorithm for pseudodisks and for fat objects. So far, O(n polylogn) SSSP algorithms were not even known for pseudodisks that are fat and convex and similarly-sized.

An almost polynomial time approximation scheme for the Euclidean Capacitated Vehicle Routing Problem (René Sitters): The Vehicle Routing Problem (VRP) is a fundamental optimization problem in Operations Research and theoretical computer science and has been studied in many variations. It has been a long-standing conjecture that a Polynomial Time Approximation Scheme (PTAS) for the Euclidean CVRP should exist. We make a big step towards proving this conjecture and present a quasi-PTAS for the capacitated VRP, where the running time is n^{O(log(log n))}. This is a major improvement over the best-known running time. Very recently (forthcoming FOCS2026) this has been improved to a real PTAS. 

MIPco = coRE (STOC Best Student Paper Award, Junqiao Lin): Interactive proof systems become dramatically more powerful when multiple unbounded provers may share quantum resources. The landmark theorem MIP*=RE shows that, with tensor-product entanglement, these systems recognize exactly the recursively enumerable languages. In this talk, I will discuss what changes when the provers instead use the commuting-operator model, which allows infinite-dimensional strategies. I will present the result MIPco=coRE, showing that these two natural models of quantum correlations lead to fundamentally different computational powers. I will then outline a unified compression framework for proving both results, based on a new weak compressibility condition, and sketch why the compression procedure extends to commuting-operator strategies. I will conclude with consequences for nonlocal games and computability questions in operator algebras.

Approximation Ratio of the Min-degree Greedy Algorithm for Maximum Independent Set on interval and chordal graphs (Steven Kelk): Here we prove that the minimum-degree greedy algorithm, with adversarial tie-breaking, is a (2/3)-approximation for the Maximum Independent Set problem on interval graphs. We show that this is tight, even on unit interval graphs of maximum degree 3. We show that on chordal graphs, the greedy algorithm is a (1/2)-approximation and that this is again tight. These results contrast with the known (tight) approximation ratio of 3/(\Delta+2) of the greedy algorithm for general graphs of maximum degree \Delta.  Based on joint work with Steven Chaplick, Martin Frohn, Johan Lottermoser and Matus Mihalak.