Bremen-Hamburg Initiative on Algorithms, Combinatorics and Optimization, May 2025
The upcoming edition of the Bremen-Hamburg workshop will take place on May 13th and 14th 2025 at the Department of Informatics (Informatikum) at the University of Hamburg, which is located in Vogt-Kölln-Straße 30, 22527 Hamburg. On both days, the program starts at 10 a.m. in room G-228 (building/"Haus" G, top floor). You can find directions to the Informatikum here.
Program Overview
Broadly, the program is as follows:
• Day 1 (Tuesday, May 13th): Research Talks. Talk slots are generally one hour, with about 45 minutes for the talk itself and the remainder for questions and discussions. There will be ample time for further discussions during breaks.
• Day 2 (Wednesday, May 14th): Open Problem session, followed by work on the problems in groups.
For the open problem session, please submit one or more problem suggestions in advance to: maurice.rolvien"AT"uni-hamburg.de
Preliminary Schedule (Day 1)
| 10:00-11:00 | Giovanne Santos (University of Hamburg): Canonical Ramsey Numbers for Partite Hypergraphs |
| 11:00-11:30 | Coffee break |
| 11:30-12:00 | Florian Chudigiewitsch (University of Lübeck): On the Complexity of Graph Modification to First-Order Definable Properties |
| 12:00-12:30 | Ebrahim Ghorbani (TU Hamburg): Quasi-Polynomial Time and Polynomial-Time Algorithms for Multi-Arrival |
| 12:30-14:00 | Lunch break (lunch will be provided) |
| 14:00-15:00 | Alexander Lindermayer (University of Bremen): A Little Clairvoyance Is All You Need for Minimizing Total Flow Time |
| 15:00-15:30 | Kim-Manuel Klein (University of Lübeck): Faster Lattice Basis Computation via a Natural Generalization of the Euclidean Algorithm |
| 15:30-16:00 | Coffee break (with cake) |
| 16:00-17:00 | Robin Labryga (University of Hamburg): Information Preserving Line Search via Bayesian Optimization |
| 17:00-17:30 | Raul Wayne Teixeira Lopes (TU Hamburg): Revisiting Directed Disjoint Paths on tournaments (and relatives) |
Talk abstracts
More abstracts to follow.
Guivanne Santos - Canonical Ramsey numbers for partite hypergraphs
Ramsey's theorem states that for sufficiently large n, any r-colouring of the edges of the complete k-uniform hypergraph on n vertices contains a monochromatic copy of the complete k-uniform hypergraph on t vertices. Erdős and Rado generalised this result to an unbounded number of colours. They characterised all canonical colour patterns that are unavoidable in edge colourings of sufficiently large complete hypergraphs. We consider quantitative aspects of this result. For Erdős and Rado's theorem, both the lower and upper bound on n grow as (k-1)-times iterated exponential polynomials of t. We show that for k-partite k-uniform hypergraphs the upper bound on n grows single exponentially.
This is joint work with Matías Azócar Carvajal and Mathias Schacht.
Florian Chudigiewitsch - On the Complexity of Graph Modification to First-Order Definable Properties
Graph modification problems are studied intensively in classical and parameterized complexity theory. The question in these problems is whether we can make at most k modifications to an input graph such that the resulting graph has a certain property. The modifications include deleting vertices, deleting or adding edges and editing the edge set. Even if the property is first-order definable, these problems can be intractable. For example, the question whether we can delete at most k vertices from a graph such that the graph becomes edgeless is equivalent to the vertex cover problem. To be able to identify fragments of first-order logic for which these problems are tractable, we investigate the quantifier pattern of the formula. In this talk, we give an overview of recent classification results based on quantifier patterns.
Ebrahim Ghorbani - Quasi-Polynomial Time and Polynomial-Time Algorithms for Multi-Arrival
Consider particle routing in a network from a source to a sink, where movement is governed by a state-dependent rule: upon visiting a node v, a particle departs via the next outgoing arc in a predefined cyclic order specific to that node. Deciding whether the sink is reachable by a single particle in such a network is known as the Arrival problem. This problem lies in the class NP ∩ co-NP, though its solvability in polynomial time remains open. In this talk, I consider Multi-Arrival, an extension of the original problem that accounts for potentially exponentially many particles moving simultaneously. The goal is to compute the final distribution of particles in the sinks, given an initial configuration. A quasi-polynomial-time algorithm for Multi-Arrival on the class of tree-like directed multigraphs will be presented, which in the case of bounded contracted height, yields a polynomial-time algorithm.
This is joint work with Jonah Leander Hoff and Matthias Mnich.
Alexander Lindermayer - A Little Clairvoyance Is All You Need for Minimizing Total Flow Time
We study the problem of preemptively minimizing the total flow time on a single machine where jobs arrive online over time. When processing times are known at arrival (called clairvoyant scheduling), scheduling at any time the job with the shortest remaining processing time is optimal. However, in non-clairvoyant scheduling, where the processing time of a job is only revealed at its completion, strong lower bounds rule out constant competitive algorithms. Therefore, this problem has been very successfully studied in models with resource augmentation or with additional information available upon the arrival of a job. We continue this line of research and consider a first model that captures practical scenarios such as profiling techniques that model a learning process while we process jobs. Specifically, for any α between 0 and 1, an α-clairvoyant algorithm learns about a job's processing time after it finished an α-fraction of the job. We present a natural algorithm based on fair allocation and the optimism principle with a constant competitive ratio of ceiling(1/(1-α). Moreover, we show that this ratio is optimal for deterministic α-clairvoyant algorithms.
This is joint work with Anupam Gupta, Haim Kaplan, Jens Schlöter, and Sorrachai Yingchareonthawornchai.
Kim-Manuel Klein - Faster Lattice Basis Computation via a Natural Generalization of the Euclidean Algorithm
The Euclidean algorithm the oldest algorithms known to mankind. Given two integral numbers a₁ and a₂, it computes the greatest common divisor (gcd) of a₁ and a₂ in a very elegant way. From a lattice perspective, it computes a basis of the sum of two one-dimensional lattices a₁ ℤ and a₂ ℤ as gcd(a₁,a₂) ℤ = a₁ ℤ + a₂ ℤ. In this paper, we show that the classical Euclidean algorithm can be adapted in a very natural way to compute a basis of a general lattice L(A₁, ... , Aₙ) given vectors A₁, ..., Aₙ ∈ ℤd with n > rank(a₁, ..., ad). Similar to the Euclidean algorithm, our algorithm is very easy to describe and implement and can be written within 12 lines of pseudocode.
Our generalized version of the Euclidean algorithm allows for several degrees of freedom in the pivoting process. Hence, in a second step, we show that this freedom can be exploited to make the algorithm perform more efficiently. As our main result, we obtain an algorithm to compute a lattice basis for given vectors A₁, ..., Aₙ ∈ ℤd in time (counting bit operations) LS + Õ((n-d)d² · log(||A||), where LS is the time required to obtain the exact fractional solution of a certain system of linear equalities.
Robin Labryga - Information Preserving Line Search via Bayesian Optimization
Line search is a fundamental part of iterative optimization methods for unconstrained and bound-constrained optimization problems to determine suitable step lengths that provide sufficient improvement in each iteration. Traditional line search methods are based on iterative interval refinement, where valuable information about function value and gradient is discarded in each iteration. We propose a line search method via Bayesian optimization, preserving and utilizing otherwise discarded information to improve step-length choices. Our approach is guaranteed to converge and shows superior performance compared to state-of-the-art methods based on empirical tests on the challenging unconstrained and bound-constrained optimization problems from the CUTEst test set.
Raul Wayne Teixeira Lopes - Revisiting Directed Disjoint Paths on tournaments (and relatives)
In the Directed Disjoint Paths problem (k-DDP), we are given a digraph and k pairs of terminals, and the goal is to find k pairwise vertex-disjoint paths connecting each pair of terminals. Bang-Jensen and Thomassen in 1992 claimed that k-DDP is NP-complete on tournaments, and this result triggered a very active line of research about the complexity of the problem on tournaments and natural superclasses. We identify a flaw in their proof, which has been acknowledged by the authors, and provide a new NP-completeness proof. From an algorithmic point of view, Fomin and Pilipczuk in 2019 provided an FPT algorithm for the edge-disjoint version of the problem on semicomplete digraphs, and showed that their technique cannot work for the vertex-disjoint version. We overcome this obstacle by showing that the version of k-DDP where we allow congestion c on the vertices is FPT on semicomplete digraphs provided that c is greater than k/2. This is based on a quite elaborate irrelevant vertex argument inspired by the edge-disjoint version, and we show that our choice of c is best possible for this technique, with a counterexample with no irrelevant vertices when c≤k/2. We also prove that k-DDP on digraphs that can be partitioned into h semicomplete digraphs is W[1]-hard parameterized by k+h, which shows that the XP algorithm presented by Chudnovsky, Scott, and Seymour in 2019 is essentially optimal.
This is joint work with Ignasi Sau and Guilherme C. M. Gomes.