The 29th Workshop on Future Research in Combinatorial Optimization took place
from August 10th to August 14th, 2026, at the
Technische Universität Berlin (TUB), Germany.
About FRICO
FRICO is directed at PhD students from the following research areas:
Discrete Mathematics and Combinatorics
Approximation Algorithms
(Mixed Integer) Linear and Non-Linear Optimization
Applications of Combinatorial Optimization
Scheduling
Randomized Algorithms
Online Optimization
Every participant was assigned a slot; either for a
25-minute presentation (plus 5 minutes for setup and questions),
or a 5-minute elevator pitch talk. It was especially encouraged to present ongoing research and open problems.
FRICO 2026 has concluded!
We are happy to announce that FRICO 2026 has concluded successfully! We thank all participants for their contributions and our sponsors for their generous support.
Next Location: The 30th Workshop on Future Research in Combinatorial Optimization (FRICO 2027) will take place at Universität Bremen. We hope to see you there!
FRICO 2026 Award Winners
Congratulations to Timo Ottiger for winning the FRICO Best Talk Award 2026! We also want to congratulate the runners-up: Rabea Freese (second place) and Simon Keil (third place).
Congratulations to Denise Graafsma for winning the FRICO Best Elevator Pitch Award 2026!
FRICO 2026 did not have a conference fee.
This was made possible by the generous support of our sponsors.
Academic Partner
MATH+ – Berlin Mathematics Research Center
Industry Sponsors
Main Sponsors
Supporting Sponsors
During the 'industry session' on Wednesday, August 12th, the sponsors informed us about the practical applications of combinatorial optimization in their companies.
To get a general impression of FRICO, visit the webpage of
FRICO 2025,
which took place in Aachen, or have a look at the
history of FRICO.
If you have any questions, please contact any of the organizers or write an email to
frico26@math.tu-berlin.de.
The team thanks Dorothea Kiefer and Martin Skutella and other university staff for their support and assistance in organizing this workshop. We are grateful to Karlotta Blankertz for her help with FRICO 2026 design, and to Philipp Warode for his support with the website. Additional thanks to our volunteers Cara Bennett, Lucas Burggraf, Malte Grabmüller and David Szymanowsky for their assistance.
Schedule
Time
10 August
11 August
12 August
13 August
14 August
9:00 - 9:30
Registration
Session D (Extremal and Structural Combinatorics)
Chair: Ekin Ergen
09:00-09:30 Johannes Schmucker (Uni Klagenfurt)
09:30-10:00 Renée Lamsfuß (Uni Wuppertal)
10:00-10:30 Laurin Schwartze (Ulm University)
Session G (Graphs and Graph Algorithms)
Chair: Frederic Horn
09:00-09:30 Sarah Feldmann (OVGU Magdeburg)
09:30-10:00 Thilo Hartel (Ulm University)
10:00-10:30 Philipp Wolf Schleicher (BTU Cottbus-Senftenberg)
Session J (Multidimensional Optimization)
Chair: Ekin Ergen
09:00-09:30 Rabea Freese (Uni Wuppertal)
09:30-10:00 Chiara Weuste (Uni Wuppertal)
10:00-10:30 Carina Truschel (Uni Konstanz)
Session N (TSP)
Chair: Sarah Feldmann
09:00-09:30 Sophia Heimann (Uni Bonn)
09:30-10:00 Malte Schürks (Uni Bonn)
9:30 - 10:00
10:00 - 10:30
Opening remarks
Break
10:30 - 11:00
Session A (Scheduling)
Chair: Ekin Ergen
10:30-11:00 Morten Weber (Uni Bremen)
11:00-11:30 PJ van Mill (Maastricht University)
11:30-12:00 Johanna Leweke (RWTH Aachen)
Break
Break
Break
Session O (Cyclic Transversal Polytopes)
Chair: Eva Ley
10:30-11:00 Jannik Trappe (OVGU Magdeburg)
11:00-11:30 Frederic Horn (OVGU Magdeburg)
11:00 - 11:30
Session E (Flows over Time)
Chair: Ekin Ergen
11:00-11:30 Dario van den Boom (RWTH Aachen)
11:30-12:00 Laura Ritter (RWTH Aachen)
Session H (Bilevel Optimization)
Chair: Paul Lippke
11:00-11:30 Eva Ley (TU Braunschweig)
11:30-12:00 Vladimir Stadnichuk (University of Kassel)
Session K (Matroids)
Chair: Paul Lippke
11:00-11:30 Áron Jánosik (ELTE Budapest)
11:30-12:00 Bence Mátravölgyi (IDSIA, USI-SUPSI)
11:30 - 12:00
Break
12:00 - 13:00
Lunch
Lunch
Lunch
Lunch
Best talk voting and closing remarks
13:00 - 13:30
Session B (Mathematical Programming)
Chair: Vladimir Stadnichuk
13:00-13:30 Eleon Bach (TU Munich)
13:30-14:00 Simon Keil (TU Munich)
14:00-14:30 Ties Schalij (Tilburg University)
Session F (Niklas and Elevator Pitch Talks II)
Chair: Lennart Kauther
13:00-13:30 Niklas Dahlmeier (RWTH Aachen)
13:30-14:00 Elevator Pitch talks: Raoul, Eva, Denise, Niklas F.
Session I (Applications)
Chair: Denise Graafsma
13:00-13:30 Timo Ottiger (ETH Zurich)
13:30-14:00 Armin Settels (Uni Bonn)
Session L (Transportation Design)
Chair: Stefan Rogosinski
13:00-13:30 Lennart Kauther (RWTH Aachen)
13:30-14:00 Nele Pommerening (TU Dortmund)
13:30 - 14:00
14:00 - 14:30
Social activities:Bundestag, Wannsee, city tour
Break
Break
14:30 - 15:00
Break
Industry Session Chair: Srinwanti Debgupta
Session M (Algorithmic Game Theory and Fair Division)
Chair: Paul Lippke
14:30-15:00 Stefan Rogosinski (RWTH Aachen)
15:00-15:30 Karolina Tammemaa (TUHH)
15:30-16:00 Ethan Williams (TU Graz)
15:00 - 15:30
Session C (Elevator Pitch Talks I)
Chair: Srinwanti Debgupta
15:00-15:30 Elevator Pitch talks: Paula, Bruno, Henning
Beyond Smoothed Analysis: Analyzing the Simplex Method by the Book
Show abstract
Narrowing the gap between theory and practice is a longstanding goal of the algorithm analysis community. In this talk we discuss the new by the book algorithm analysis framework.
In contrast to earlier frameworks, by-the-book analysis not only models an algorithm’s input data, but also the algorithm itself. Results from by the book analysis are meant to correspond well with established knowledge of an algorithm’s practical behavior, as they are meant to be grounded in observations from implementations, input modeling best practices, and measurements on practical benchmark instances.
Furthermore, we apply our framework to the simplex method, an algorithm which is beloved for its excellent performance in practice and notorious for its high running time under worst-case analysis.
The simplex method similarly showcased the state of the art framework smoothed analysis (Spielman and Teng, STOC’01).
We prove that under input scaling assumptions, feasibility tolerances and other design principles used by simplex method implementations, the simplex method indeed attains a polynomial running time. This is joint work with Alexander Black, Sophie Huiberts and Sean Kafer and appeared at STOC'26.
Paula Boettger (IDSIA, USI-SUPSI)Session C (Elevator Pitch Talks I)
Three-Dimensional Knapsack Problem with Resource Augmentation
Show abstract
In the three-dimensional knapsack problem (3DK), we are given a unit-cube knapsack and a set of axis-aligned cuboids with associated profits. The objective is to find a non-overlapping axis-aligned packing (by translation) of a subset of the items into the knapsack. The current best approximation algorithm for 3DK is a $(139/29+\varepsilon)\approx4.794+\varepsilon$-approximation due to Jansen et al.. We present a polynomial-time $(2+\varepsilon)$-approximation algorithm for 3DK with resource augmentation, where the knapsack is enlarged to $[0,1+\varepsilon]\times[0,1+\varepsilon]\times[0,1]$. Our approach extends the concept of container packing, introduced by Jansen et al., to the resource augmentation setting. A container packing is a structured packing of the knapsack, and a near-optimal such packing can be computed efficiently. With resource augmentation, we show the existence of an augmented container packing with significantly higher profit. The key ingredient is a novel decomposition of an optimal packing into regions that can be repacked as strips.
Dario van den Boom (RWTH Aachen)Session E (Flows over Time)
The Piñata Method
Show abstract
Transshipments over time are the counterpart to classical $b$-flows in the field of network flows over time, and referred to as "arguably the most difficult flow over time problem that can still be solved in polynomial time'' (Skutella, 2023). Recent results by Anapolska et al. (2025) have significantly advanced the state-of-the-art runtime for the integral transshipment over time problem from $\tilde{\mathcal{O}}(m^4 k^{15})$ by Hoppe and Tardos (2000) down to $\tilde{\mathcal{O}}(m^2 k^5 + m^4 k^2)$, where $m$ is the number of arcs and $k$ is the number of terminals. In this paper, we improve upon these results and reduce the runtime further down to $\tilde{\mathcal{O}}(m^2 k^4 + m^3 k)$. In the likely case of $m\lt k^4$, we even outperform the current state-of-the-art runtime for computing fractional transshipments over time of $\tilde{\mathcal{O}}(m^2 k^5)$ by Schlöter and Skutella (2017), thus closing the computational gap between the integral and fractional transshipment over time problem.
Bruno Borchardt (Hamburg University of Technology)Session C (Elevator Pitch Talks I)
Approximating Buy-at-Bulk on Grids
Show abstract
We consider an extremal case of the buy-at-bulk problem with a single root. Formally, we are given a graph with weighted edges, a subset of the vertices called terminals and a special vertex called the root. The goal is to find a minimum-weight subgraph that connects each terminal to the root via a shortest path. This is extremal in the sense that the usual buy-at-bulk setting allows detours, but they will increase the cost of a solution. Our restriction still retains many routing options on grids and grid-like graphs, as here, on average, a constant fraction of all vertices lie on a shortest path between two random vertices.
We solve this setting via a transformation to an integer linear program. Our approach tests for each pair of terminals for how long shortest paths from the root to either terminal can intersect. The ILP variables correspond to these furthest intersection points of potentially chosen paths. The size of the ILP thus mostly depends on the number of terminals and their relative arrangement, not the refinement level of the grid.
Eva Bradbrook (ETH Zurich)Session F (Niklas and Elevator Pitch Talks II)
Strong Timetabling via Fast and Smart Neighbourhoods
Show abstract
University course timetabling is a complex real-world problem. Although it can readily be modelled as a mixed-integer program (MIP), exact solutions are intractable beyond simple instances. We design optimisation problems that identify small neighbourhoods of a current solution likely to contain improvements, then explore them - e.g., via much smaller MIPs solvable exactly even for large instances. The goal is a fast, strong timetabling algorithm, practical and easily adaptable to real-world settings.
Niklas Dahlmeier (RWTH Aachen)Session F (Niklas and Elevator Pitch Talks II)
ResearchGate ↗
A 2-Approximation for Graphic Multi-Path TSP
Show abstract
The Multi-Path TSP is a generalization of the classic Path TSP where, instead of a single source-sink pair, we are given multiple pairs to connect while ensuring all vertices are visited. While the current best-known approximation ratio for the general problem is 2.214 (Böhm et al., SODA 2025), this talk focuses on the case of graphic metrics.
We present a 2-approximation algorithm for Graphic Multi-Path TSP. Our approach relies on decomposing the flow from an optimal LP solution, sampling paths from this decomposition, and connecting the remaining vertices using doubled edges. We show that the cost of the sampled paths can be absorbed into the doubled edges, maintaining a factor-2 guarantee. Lastly, we touch upon a reduction showing that a below-2 approximation for the special case where each source equals its corresponding sink would imply a below-2 approximation for the general Graphic Multi-Path TSP.
Sarah Feldmann (Otto-von-Guericke University Magdeburg)Session G (Graphs and Graph Algorithms)
The Path Intersection Problem
Show abstract
During the study of doubly resolving sets, I discovered a related problem, the path intersection problem. The goal is, given a graph $G=(V,E)$ we want to find a minimum subset $B\subseteq V$ that fulfills the following property: For $v,b\in V$ let $P_{v,b}$ be the union of all shortest $v$-$b$-paths. Then, there exist two vertices $b_1,b_2 \in B$ such that $P_{v,b_1} \cap P_{v,b_2} = \{v\}$.
In my talk, I introduce the path intersection problem and the relation to the doubly resolving set problem and show that the decision version is NP-hard with a reduction from the dominating set problem. Afterwards, I prove an approximation lower bound for the path intersection problem.
Rabea Freese (University of Wuppertal)Session J (Multidimensional Optimization)
From Finding Safe Routes for Children to School to Solving High Dimensional Ordinal Optimization Problems
Show abstract
A parent's decision on which route they send their child to school can differ significantly from what an "optimal" shortest path looks like. In this application in addition to minimizing the distance one might want to consider the child's safety as an additional factor.
Thus, we study an optimization approach using an ordinal cost function measuring the safety of paths on street networks in order to provide users with more suitable solutions. These problems are transformed into multi-objective shortest path problems which can be solved using the multiobjective Dijkstra algorithm. However, since pedestrians only accept very minor detours and prefer e.g. routes with fewer turns, in practice we need a very specific subset of the resulting Pareto-front. To compensate for that we develop a solution strategy using Yen's $k$-shortest path algorithm and pair it with different filtering steps to obtain a set of solutions optimal in the original instance. These are specifically tailored to footpath routing without having to solve a very high-dimensional optimization problem and without having too many solutions to choose from.
Niklas Füller (BTU Cottbus-Senftenberg)Session F (Niklas and Elevator Pitch Talks II)
A Combinatorial Model for Water Networks
Show abstract
A growing number of components and constraints in heating networks make it essential to be able to calculate the frequently changing heat distribution quickly and efficiently. As a basis for these calculations, the hydraulic variables (pressure, volume flow rate) of the transport medium (usually water) must be calculated for all edges of the heating network. The usual approach to this problem in practice is to solve a corresponding nonlinear system of equations.
We show how this problem can be solved efficiently using tools from combinatorial optimization, in particular, the problem can be formulated as a non-linear single-commodity min-cost flow problem.
Denise Graafsma (University of Twente)Session F (Niklas and Elevator Pitch Talks II)
Chasing Functions on the Line with Predictions
Show abstract
Function chasing is an online optimization problem that models real-world scenarios such as load balancing in data centers. We consider the one dimensional version of the problem, where functions are chased on the line. An instance consists of multiple rounds. During each round a new function appears. We can respond by moving to a new point on the line. The cost incurred in a round is the distance moved plus the value of the function at the new position. The goal is to minimize the total cost. However, since the problem is online, we must decide where to move without knowing the future functions.
In practice, one often has some idea of what future functions will look like. For example, in the data center setting, operators typically have access to predictions of future energy costs. We study how such predictions can be incorporated into the decision-making process. Unlike the previously studied black-box prediction model, where the best move for the current round is predicted, we consider a setting in which all future functions are predicted.
Thilo Hartel (Ulm University)Session G (Graphs and Graph Algorithms)
Forest cuts in sparse graphs
Show abstract
A forest cut in a simple graph is a vertex cut that induces a forest.
Chernyshev, Rauch and Rautenbach [1] proposed the conjecture that every
graph $G$ of order $n$ with less than $3n − 6$ edges has a forest cut. While this
conjecture has been verified for planar graphs [1], it is still open for general
graphs. The current best lower bound for general connected graphs is due
to Bogdanov et al. [2], who proved that a connected graph with $n$ vertices
and less than $19n−28$ edges admits a forest cut.
A Near-Complete Resolution of the Exponential-Time Complexity of $k$-opt for the Traveling Salesman Problem
Show abstract
The $k$-opt algorithm is one of the simplest and most widely used heuristics for solving the traveling salesman problem. Starting from an arbitrary tour, the $k$-opt algorithm improves the current tour in each iteration by exchanging up to $k$ edges. The algorithm continues until no further improvement of this kind is possible. For a long time, it remained an open question how many iterations the $k$-opt algorithm might require for small values
of $k$, assuming the use of an optimal pivot rule. In this paper, we resolve this question for the cases $k = 3$ and $k= 4$ by proving that in both these cases an exponential number of iterations may be needed even if an optimal pivot rule is used. Combined with a recent result by Heimann, Hoang, and Hougardy (ICALP 2024), this provides a complete answer for all $k \geq 3$ regarding the number of iterations the $k$-opt algorithm may require under an
optimal pivot rule. In addition we establish an analogous exponential lower bound for the 2.5-opt algorithm, a variant that generalizes 2-opt and is a restricted version of 3-opt. All our results hold for both the general and the metric traveling salesman problem. (This is joint work with Hung P. Hoang and Stefan Hougardy.)
Frederic Horn (Otto-von-Guericke University Magdeburg)Session O (Cyclic Transversal Polytopes)
Cyclic Transversal Polytopes: An Algebraic Toolbox for Combinatorial Optimization
Show abstract
Cyclic Transversal Polytopes (CTPs) arise from a simple combinatorial selection problem: given several finite sets of elements from a finite abelian group, one selects one element from each set such that all selected elements sum to zero; the CTP is the convex hull of all such selections. This algebraic perspective yields a flexible modeling language for combinatorial optimization problems. The talk focuses on the facet structure of CTPs, in particular Countdown inequalities, a family of valid inequalities connected to Gomory's master corner polyhedron. We present constructions determining exactly when strong combinatorial inequalities, such as clique inequalities, can be realized within this framework.
Áron Jánosik (ELTE Budapest)Session K (Matroids)
Hypergraph Representation of All Matroids
Show abstract
The Crapo-Rota conjecture suggests that the asymptotic fraction of paving matroids on
n elements tends to 1 as n tends to infinity. A consequence of this conjecture would be that almost all matroids share a similar underlying hypergraph structure. This raises the question: is there a similar, even more general underlying structure for all matroids? Building upon a definition by Balcan and Harvey, we demonstrate that with a slight modification, the resulting class, which we introduce as cuptroids, provides such a structure. Furthermore, we define the class of captroids and examine various extensions of these concepts. We prove that cuptroids and captroids are duals of each other and are closed under taking minors while keeping the original structure. Finally, we establish additional properties concerning submodularity-modularity and the cyclic flat lattice, while highlighting several open problems that remain for these new matroid classes.
Henning Jasper (Osnabrück University)Session C (Elevator Pitch Talks I)
Solving the Minimum-Stretch Minimum-Weight Spanning Tree Problem
Show abstract
We investigate the Minimum-Stretch Minimum-Weight Spanning Tree (MS-MWST) problem.
Given an undirected graph with independent weights and lengths on edges, find a minimum-weight spanning tree that minimizes the maximum stretch factor, i.e., the maximum ratio of any node pair's distance in the original graph to their distance in the tree.
Existing literature (almost) exclusively focuses on the ``basic'' case where all weights and lengths are 1.
This variant is known to be NP-hard and NP-hard to approximate with any ratio better than 5/4.
The only known approximation algorithm achieves a ratio of O(log n).
An exact ILP formulation has been proposed and evaluated in practice. However, it is unable to solve instances with more than 20 nodes.
Recently, an FPT algorithm parameterized in the treewidth was proposed.
I am interested in finding approximate or exact solution approaches for the MS-MWST for arbitrary, independent weights and lengths.
All of my initial ideas have encountered fundamental challenges.
Therefore, I would like to use my elevator pitch to present this as an open problem in order to find collaborators.
As I intend to implement and use such an algorithm in practice as a subroutine, practicality would be a central focus.
Lennart Kauther (RWTH Aachen)Session L (Transportation Design)
Fare Zone Assignment on Trees
Show abstract
Fare design in public transportation networks is an important challenge. A popular approach is to partition the network into fare zones ("zoning'') and fix journey prices depending on the number of traversed zones ("pricing''). In this paper, we focus on finding revenue-optimal solutions to the zoning problem for a given subadditive pricing function. We consider tree networks with n vertices, since trees already pose non-trivial algorithmic challenges. Our main results are efficient algorithms that yield a simple $O(log n)$-approximation as well as a more involved $O(log n/ log log n)$-approximation. We show how to solve the problem exactly on rooted instances, in which all demand arises at the same source, and show APX-hardness for general instances on star graphs. For paths, we prove strong NP-hardness and outline a PTAS. Moreover, we show that computing an optimal solution is in FPT or XP for several natural problem parameters.
Minimal sizes of linear relaxations in integer programming
Show abstract
A central theme in combinatorial optimization is to represent a set of feasible solutions as a set of integer points X in an appropriate space and to optimize a linear function over them. To treat this problem algorithmically, a common approach is to devise a system of linear inequalities whose feasible integer points are precisely X. The smallest number of inequalities in such a system that does not use auxiliary variables is called the relaxation complexity rc(X).
In this talk, we discuss the relaxation complexity of the arguably simplest full-dimensional set of integer points, the discrete standard simplex. Surprisingly, the number of inequalities needed in a relaxation depends strongly on the coefficients that are allowed: While it is known that a linear number of inequalities is needed when only using rational coefficients, we present an explicit and elementary construction showing that a logarithmic number of inequalities suffices when irrational coefficients are allowed.
Renée Lamsfuß (University of Wuppertal)Session D (Extremal and Structural Combinatorics)
Constructing Low Discrepancy Point Sets on the Triangle
Show abstract
In this talk, we construct low discrepancy point sets on the triangle.
The $L_\infty$ star discrepancy is one of the most common measures used to quantify the uniformity of a point set on the unit square. This measure is based on two proportions: We define boxes in the unit square, and evaluate the absolute difference between the proportion of the total volume that is covered by this box and the proportion of points that lie inside of this box. The worst absolute difference over all possible boxes in the unit square defines the discrepancy value of the point set.
We generalize this concept to triangles and introduce a mathematical programming formulation to construct point sets with a minimal star discrepancy on the right-angled triangle. Therefore, we discretize the discrepancy problem and
obtain a mixed-integer non-linear program. With the parallelogram discrepancy, we review another discrepancy measure that quantifies the distribution of point sets on arbitrary triangles. We highlight the connections between both discrepancy measures and compare our point sets with other low discrepancy points sets on the triangle.
Johanna Leweke (RWTH Aachen)Session A (Scheduling)
On the complexity of integrated patient admission scheduling and room assignment
Show abstract
We study an integrated admission scheduling and room assignment problem arising in hospitals. Patients have prescribed admission windows and fixed lengths of stay. The goal is to choose an admission day for each patient such that a feasible room assignment exists throughout the planning horizon, respecting room capacities and gender separation, while allowing patient transfers between rooms.
In this talk, we investigate the computational complexity of this integrated problem. We show that introducing gender separation renders the feasibility problem NP-complete, whereas the variant without compatibility constraints is solvable in polynomial time. We further identify several polynomially solvable special cases, including instances in which all patients have the same length of stay and at most two feasible admission days. Finally, we discuss several natural extensions of the problem and outline open questions for future research.
Inverse optimization problems are bilevel problems in which the leader modifies the follower's objective such that a prescribed feasible solution becomes an optimal solution of the follower. They capture hierarchical decision-making problems like parameter estimation tasks or situations where a planner wants to steer an agent's choice.
In integral inverse optimization problems, the leader's cost modifications must be integral.
Adding this integrality constraint for the cost modifications changes some inverse optimization problems like the inverse linear problem, the inverse matching problem on a non-bipartite graph or the inverse knapsack problem. In contrast, other inverse problems like the inverse shortest path problem, the inverse min cut problem or the inverse min spanning tree problem have an optimal integral solution without loss of generality if all original weights are integer.
We prove that the integral inverse mixed-integer problem lies in coNP, similar to the (continuous) inverse mixed-integer problem. Thus, for example, the integral inverse knapsack problem is coNP-complete which was previously an open question in the literature.
Jakob Lindner (RWTH Aachen)Session C (Elevator Pitch Talks I)
Ordinal Hegselmann-Krause Systems
Show abstract
Opinion formation shapes modern societies. The study of most bounded‑confidence models, most notably the Hegselmann‑Krause system (HKS), rely on averaging, a rule that is often at odds with empirical findings from psychology and social choice. This work replaces the average with ordinal aggregation functions, focusing on the median and a family of “k‑large’’ rules, and examines the resulting convergence properties. For asynchronous best‑response dynamics we show that median‑based updates always reach an equilibrium in polynomial time, while any ordinal aggregation is weakly‑acyclic: an improving sequence to equilibrium exists from every initial state, although cyclic trajectories can occur. The k‑large rule, where each agent adopts the k-largest neighbour opinion, enjoys the finite‑improvement property, guaranteeing termination of asynchronous dynamics; random selection of the updating agent yields polynomial‑expected convergence time. For synchronous updates, a broad class of ordinal aggregations, including the median and all k‑large rules, lead to linear‑time convergence. To the best of our knowledge, these results provide the first systematic characterization of ordinal aggregation in HKS, highlighting when realistic, non‑averaging opinion updates still ensure rapid stabilization of collective opinions.
Raoul Luqué (RWTH Aachen)Session F (Niklas and Elevator Pitch Talks II)
A 1.5-Approximation for Graphic Multi-Depot Multiple TSP
Show abstract
The Graphic Multi-Depot Multiple TSP is an interesting generalization of the classic Graphic TSP. Instead of a single tour, the objective is to find a collection of tours that visit all non-depot vertices at least once while minimizing the total number of edges used. Each tour must also visit at least one of the depot vertices.
Current best-known approximation algorithms provide a 2-approximation when the number of depots becomes arbitrarily large. We improve upon this by using an altered version of the Christofides-Serdyukov algorithm, resulting in a 1.5-approximation. Previous approaches have only achieved such approximation guarantees for a constant number of depots, though they also considered the metric case. Lastly, the 1.5-approximation can be used to improve upon the 2-approximation ratio for the Graphic Multi-Path TSP, as presented in the talk on "A 2-Approximation for Graphic Multi-Path TSP".
There is a long list of open questions rooted in the same underlying problem: understanding the structure of bases or common bases of matroids. These conjectures suggest that matroids may possess much stronger structural properties than are currently known. One example is related to cyclic orderings of matroids. A rank-$r$ matroid is called cyclically orderable if its ground set admits a cyclic ordering such that any interval of $r$ consecutive elements forms a basis. In this paper, we show that if the ground set of a split matroid decomposes into pairwise disjoint bases, then it is cyclically orderable. This result answers a conjecture of Kajitani, Ueno, and Miyano in a special case, and also strengthens Gabow's conjecture for this class of matroids. Our proof is algorithmic, hence it provides a procedure for determining a cyclic ordering in question using a polynomial number of independence oracle calls.
PJ van Mill (Maastricht University)Session A (Scheduling)
A further investigation of Learning-SEPT
Show abstract
Joint work with André Berger and Tjark Vredeveld.
We study a problem of learning in stochastic scheduling. Jobs are divided into K classes, each of which has an unknown processing time distribution. Learning about the distribution of a class requires irrevocably scheduling jobs from the class and observing their processing time realisations.
There is a single machine and the objective is to minimise the expected sum of completion times. We study a very simple heuristic policy called Learning-SEPT, and seek to determine its approximation ratio for certain distributional assumptions.
Timo Ottiger (ETH Zürich)Session I (Applications)
Making Local Search for the CVRP 10,000 Times Faster
Show abstract
At last year’s FRICO, I presented our group's collaboration with Swiss Post. The core challenge of this partnership is the well-known Capacitated Vehicle Routing Problem (CVRP), for which we aimed to develop a high-performance local search algorithm.
This year, I want to share how we implemented this local search procedure to be extremely efficient. While the local search approach itself is already well established, I will provide insights into several clever techniques that combine low-level implementation details with algorithmic modifications to increase our execution speed by several orders of magnitude compared to a simple implementation.
Nele Pommerening (TU Dortmund)Session L (Transportation Design)
On the complexity of price-collecting Hub Location Problems with given Hubs
Show abstract
In this contribution we consider the complexity of different price-collecting Hub Location Problems. Because the original Hub Location Problem is NP-hard in the strong sense it is not surprising that a price-collecting Hub Location Problem in general is also NP-hard. This also holds if the transportation costs arise for example per vehicle and not linearly. So, we also focus on what happens if the Hub selection and the allocations are given in advance. Then the complexity differs between the cost variants. If the costs are linear the price collecting Hub Location Problem lies in P. In contrast to that variants with nonlinear costs can lie in P or be even NP-hard in the strong sense what depends on the exact variant.
Laura Ritter (RWTH Aachen)Session E (Flows over Time)
An applicable framework for convergence of equilibria in Vickrey-like traffic models
Show abstract
Dynamic traffic simulators such as MATSim model travellers as discrete agents who adapt their routes and departure times, but it is nontrivial whether equilibria of increasingly fine discrete models converge to a meaningful continuous equilibrium. We prove that, under suitable arc-level convergence assumptions, equilibria in a broad class of traffic models converge to Nash flows over time, the canonical equilibrium concept for continuous flows with Vickrey bottleneck queues, a particularly well-understood model. The central tool is a delay-map framework, which assigns travel times to every agent, arc, and entry time and thereby captures both realised routes and unilateral deviations. We show that arc-level convergence of these delay maps to Vickrey behaviour is sufficient to guarantee convergence of equilibrium sink arrival times for all agents. This reduces global network convergence to local single-arc verification and avoids a model-specific analysis of error propagation through the network. We also extend the framework to settings in which agents optimise using approximate delay information, provided these estimates converge to the true delay maps. As applications, we prove convergence for MATSim equilibria as time-step and packet-size discretisations are refined. Further applications include models with time-varying transit times and capacities, heterogeneous agent-dependent travel times, limited overtaking behaviour, and predictive routing based on increasingly accurate queue forecasts. These results identify Nash flows over time as a robust limit equilibrium concept for a wide range of discrete, approximate, and perturbed traffic models whose arc dynamics converge to the Vickrey bottleneck model.
Stefan Rogosinski (RWTH Aachen)Session M (Algorithmic Game Theory and Fair Division)
Assortment optimization under the Nested Logit model for heterogeneous customers
Show abstract
In this presentation I will talk about assortment optimization under the Nested Logit model for heterogeneous customers. A firm has to decide which candidate products to offer to its customers. We assume the customers to be heterogeneous and that they follow the NL model which means that products are grouped into subsets called nests where they are correlated. The goal is to maximize the expected revenue of the firm. This problem is nonconvex and nonlinear. It is fractional and both numerator and denominator are nonlinear. We approximate them by piecewise linear functions and then apply Charnes-Cooper Transformation to linearize the program. The presentation focuses on creating efficient breakpoints. Our approach is to choose the optimal objective function values as new breakpoints and combine this with a Branch-and-Bound algorithm. This leads to an exact optimal solution.
Ties Schalij (Tilburg University)Session B (Mathematical Programming)
Reformulating nonconvex Mixed-Integer Quadratic Programs as Mixed-Integer Linear Programs
Show abstract
Mixed-integer quadratic programs (MIQPs) arise in numerous applications that combine discrete and continuous decision variables with quadratic objectives.
The difficulty of these problems is twofold: quadratic objectives may be nonconvex, and discrete restrictions on a subset of the variables induce a nonconvex feasible region.
Existing approaches to nonconvex MIQPs typically rely on spatial branch-and-bound and convex relaxations, yielding global optimality certificates only up to a prescribed tolerance. Exact methods often impose convexity assumptions on the continuous quadratic components. To the best of our knowledge, no solver exists that provides globally optimal solutions with a theoretical guarantee without this convexity assumption.
We introduce a compact exact MILP reformulation for general MIQPs whose size grows linearly with the original MIQP, and that does not require convexity of any part of the quadratic objective. The proposed reformulation enables established MILP theory, modeling tools, and computational techniques to be applied to general MIQPs and yields exact globally optimal solutions whenever the reformulated MILP is solved to optimality.
Philipp Wolf Schleicher (BTU Cottbus-Senftenberg)Session G (Graphs and Graph Algorithms)
Optimization Problems Parameterized by Simultaneous Graph Parameters
Show abstract
Beisegel, Chiarelli, Köhler, Milanič, Muršič and Scheffler [SWAT 2024] introduced the concept of simultaneous $\mathcal{C}$-numbers which associate a graph class $\mathcal{C}$ with a graph parameter. Given a graph $G$, the simultaneous $\mathcal{C}$-number is the smallest number $d$ for which there is a graph $H$ in $\mathcal{C}$ and a function $L \colon V(G) \to \mathcal{P}(\{1, \ldots, d\})$ such that two vertices $u$ and $v$ are adjacent in $G$ if and only if they are adjacent in $H$ and their sets $L(u)$ and $L(v)$ are not disjoint. Beisegel et al. focused on the class of interval graphs, giving FPT
algorithms for the problems Clique, Independent Set, and Dominating Set parameterized by the simultaneous interval number. We consider these three problems when parameterized by other simultaneous $\mathcal{C}$-numbers, namely for chordal graphs, comparability graphs, and co-comparability graphs.
Johannes Schmucker (University of Klagenfurt)Session D (Extremal and Structural Combinatorics)
MSc Thesis ↗
Symmetric Term Sparsity
Show abstract
Many problems in various fields, such as graph theory, dynamical systems, and deep learning, can be successfully modeled as polynomial optimization problems (POPs). These are optimization problems in which both the objective function and the constraints are polynomial. Over the past three decades, significant research efforts have been devoted to approximating or even solving these generally very difficult problems. In particular, this has been achieved through the moment–SOS hierarchy proposed by Lasserre and Parrilo, which approximates POPs via semidefinite programs (SDPs).
However, the size of these SDPs increases rapidly with the number of variables or the degree of the polynomials, often making them intractable on modern computers. To mitigate this issue, recent methods exploit structural properties of the polynomials, such as symmetries and sparsity. In this context, Wang, Magron, and Lasserre have proposed a hierarchy based on term sparsity, which takes advantage of polynomials with few nonzero terms.
After introducing polynomial optimization, we will propose in this talk, which is based on joint work with Daniel Brosch, a symmetric variant of the term sparsity hierarchy, allowing us to exploit the symmetries of the problem as well. To this end, we study chordal extensions of the term sparsity pattern graph that preserve the automorphism group of the term sparsity graph. In particular, we focus on the case of optimizing symmetric polynomials, that is, polynomials invariant under the action of the symmetric group, where we show that the corresponding sequence of term sparsity graphs stabilizes with respect to chordality as the number of variables increases.
Malte Schürks (University of Bonn)Session N (TSP)
Approximating the Reciprocally Metric TSP
Show abstract
We consider a new class of instances of the symmetric traveling salesman problem: Instead of requiring that the distances $c(v, w)$ are metric, we require that $c'(v, w) := \frac{1}{c(v, w)}$ is metric. We demonstrate how this problem differs from similar previously studied problems, and provide a $\frac{4}{3}$ approximation algorithm for it.
Laurin Schwartze (Ulm University)Session D (Extremal and Structural Combinatorics)
On the Extremal Graphs of Dynamic Colorings
Show abstract
Montgomery [1] introduces the notion of a dynamic k-coloring as a proper
vertex coloring $c \colon V (G) \to \{1, 2, \ldots, k\}$ such that every vertex of degree at
least two is adjacent to at least two color-classes. The dynamic chromatic
number $\chi_d(G)$ of a graph $G$ is the smallest $k$ for which a dynamic $k$-coloring
exists. Lai et al. [2] prove that $\chi_d(G) ≤ \Delta(G) + 1$ for all graphs of max-
imum degree $\Delta(G) \geq 4$. Kaprov [3] proves that for $\Delta(G)$ at least 8, the
extremal graphs for this upper bound are subdivisions of complete graphs
and conjectures that the same holds for $\Delta(G)$ at least 5. We investigate this
conjecture.
Armin Settels (University of Bonn)Session I (Applications)
SAT-Based Detailed Routing (Chip Design)
Show abstract
In detailed routing, disjoint Steiner trees have to be packed into a three-dimensional grid graph. Due to engineering limits in modern chip manufacturing, these Steiner trees have to obey many additional constraints (DRC rules).
The most difficult instances cannot be solved by path-finding and rip-up-and-reroute approaches. While integer programming algorithms are able to solve them, their memory usage is prohibitively large.
An alternative approach integrates path searches as a decision strategy into a CDCL SAT solver.
We expand on this previous approach by combining it with recent advances in CDCL SAT solving, which allow for dynamic clause adding (IPASIR-UP), obtaining a fast, complete, and memory-light solver that can be employed on modern detailed routing instances.
Vladimir Stadnichuk (University of Kassel)Session H (Bilevel Optimization)
Analyzing the Potentials of Car-Free Zones in Munich
Show abstract
Car-free zones (CFZs) are designed to reduce urban air pollution by restricting vehicle access and promoting sustainable transportation. City authorities implement CFZs to support pedestrians, cyclists, and public transport, aiming to achieve sustainability goals in transportation. However, the introduction of CFZs requires strategic planning to balance the benefits against potential negative impacts on businesses and private vehicle users. Our research addresses this challenge by focusing on the interrelation between city authorities establishing CFZs and network users adjusting their travel behaviors in response.
We employ a bilevel optimization model, with the first level representing city authorities’ decisions on CFZ locations and the second level reflecting network users’ adaptations. To make this bilevel model computationally tractable, we develop novel acceleration techniques based on smart path enumeration. We validate the proposed model and derive managerial insights from a case study in Munich, Germany. We study the impact that CFZs of varying sizes have on external cost savings and user mode choice. Furthermore, we investigate how restricting displaced car traffic from CFZs influences our results.
Karolina Tammemaa (Hamburg University of Technology)Session M (Algorithmic Game Theory and Fair Division)
Diverse Schedules for Makespan Minimization on Unrelated Machines
Show abstract
We study makespan minimization on unrelated machines with the additional goal of constructing diverse schedules.
Instead of outputting a single schedule, we seek a collection of schedules with
provable makespan guarantees and substantially different job assignments. This
setting is motivated by practical applications in which committing to a single
schedule in advance may be undesirable. Processing times may be uncertain, and
additional constraints or domain knowledge may become available only later, so
providing a set of $k$ schedules of similar quality gives the scheduler meaningful
alternatives.
We measure pairwise diversity by the weighted Hamming distance between job
assignments and study the two standard objectives in the diverse-solutions
literature: max-sum diversity, which maximizes the total pairwise distance between
schedules, and max-min diversity, which maximizes the smallest pairwise
distance.
Jannik Trappe (Otto-von-Guericke University Magdeburg)Session O (Cyclic Transversal Polytopes)
Cyclic Transversal Polytopes: A Generalization of the Parity Polytope
Show abstract
Many interesting polytopes, such as matching, stable set, and cut polytopes, are isomorphic to cyclic transversal polytopes, a generalization of the parity polytope defined by Frede, Kaibel, and Merkert in 2024. We generalize Jeroslow's inequality for the parity polytope to lifted odd set inequalities for cyclic transversal polytopes and identify them as the common origin for Edmonds' inequalities for matching polytopes, the odd hole inequalities for stable set polytopes, and the cycle inequalities for cut polytopes. We generalize known extended formulations for the parity polytope to extended formulations for cyclic transversal polytopes and discuss relaxations of these formulations.
Carina Truschel (University of Konstanz)Session J (Multidimensional Optimization)
Algorithmica ↗
Subset Selection under Pareto-Dominance
Show abstract
In multi-objective optimization problems, the goal is typically to compute the set of Pareto-optimal solutions. Many algorithms for these types of problems rely on the efficient merging or combining of partial solutions and filtering of dominated solutions in the resulting sets. In this work, we tackle subset selection under Pareto-dominance in order to obtain sets of non-dominated solutions for a given optimization problem. We introduce efficient algorithms for exact subset selection of Pareto sums for multi-objective optimization problems. The Pareto sum of two Pareto sets is defined as all non-dominated elements in the Minkowski sum, i.e. the set of pairwise additions from both sets. Further, we investigate conditional lower bounds for the computation of Pareto sums using fine-grained complexity as well as approximation approaches to Pareto-optimal subset selection.
Since Pareto sets may become very large in high-dimensional optimization problems, they may overwhelm decision makers and make it difficult to select a suitable alternative. Hence, we study subset selection via regret minimization, which identifies small representative subsets of specified size while preserving decision quality under unknown user preferences. As an application, we consider multi-criteria route planning, where users may want to minimize travel time while also avoiding steep inclines, toll roads, or unpaved surfaces. We demonstrate how regret-based filtering can significantly reduce the number of alternatives while maintaining close-to-optimal choices. An extensive experimental study on synthetic and real-world data highlights the improvements in running time, space consumption, and decision support quality.
Morten Weber (University of Bremen)Session A (Scheduling)
Online Weighted Flow Time with Equal-Size Jobs
Show abstract
We study the classic online scheduling problem of minimizing total weighted flow time on a single machine with preemption, in the special but practically motivated regime where all processing times are equal or there are only k distinct processing times. This setting captures modern inference-serving and microservice platforms, where requests execute a fixed service endpoint and have different priorities depending on user service tiers. While the general problem does not admit constant-competitive deterministic algorithms, the intrinsic difficulty of the case of few processing times remains poorly understood. This holds particularly true for lower bounds, as standard adversarial arguments based on local competitiveness break down. When all processing times are equal, a folklore deterministic 2-competitive algorithm is known.
We consider two notions of competitiveness: a global one, comparing total weighted flow time against the optimum, and a local one, comparing the maximum ratio of active weight over all times, which implies the same bound on the global ratio.
Our main results are as follows. Under the global notion, we give a deterministic $3/2$-competitive algorithm for instances whose weights are powers of two. Under the local notion, we provide a tight analysis of a simplified variant of the algorithm of Azar and Touitou (FOCS '18), showing that it is 4k-competitive for equal-size jobs and 2k-competitive when weights are powers of two, where $k$ is the number of distinct processing times. On the lower-bound side, we show that every deterministic online algorithm for equal-size jobs has a competitive ratio at least $1.1804$. Moreover, we prove a tight lower bound of 2 on the local competitive ratio of any deterministic online algorithm, even when all weights are powers of two, matching our upper bound.
Chiara Weuste (University of Wuppertal)Session J (Multidimensional Optimization)
Representations for Multi-Objective Optimization Problems with General Dominance Cones
Show abstract
In this talk, we discuss different representations for discrete multi-objective optimization problems (MOPs) with a polyhedral convex dominance cone. When solving MOPs, typically even a small number of objectives already generates a large number of compromise solutions and their non-dominated outcome vectors. In order to provide the decision maker with a manageable set of alternatives we are interested in identifying a representative subset (representation). We focus on cardinality, coverage, and uniformity as our quality indicators for representations. Several approaches have been proposed to measure the latter two indicators in the context of multi-objective optimization with the Pareto cone as the dominance cone. We discuss to what extent these approaches can be transferred to more general dominance cones and whether they can be computed using existing methods developed for representation problems in multi-objective optimization.
Our focus lies on dominance-based and distance-based representations. Dominance-based approaches rely on the idea of attenuating dominance, or equivalently, enlarging the dominance cone. For distance-based measures, the choice of distance metric can influence both the resulting representation and its interpretation in the given context. Our goal is to provide an overview of the different representation approaches and to discuss their respective advantages and limitations.
Ethan Williams (TU Graz)Session M (Algorithmic Game Theory and Fair Division)
Fair Division with Dominating Set Constraints
Show abstract
In the fair division problem one must distribute a set of indivisible goods to a set of agents with the goal of ensuring that the allocation satisfies some fairness property. We present a new model where each good is a vertex in a graph, and the bundle of goods assigned to each agent must form a dominating set of that graph. We show that there is a polynomial time algorithm for computing envy-free up to one good allocations with such a dominating set constraint when the agents have identical valuations. We also provide a characterization of the graphs which always have such allocations.
Venue
FRICO 2026 was hosted by the Technische Universität Berlin (TU Berlin).
The conference took place at the ground floor of the Interdisciplinary Center for Modelling and Simulation (IMoS), located at Fasanenstraße 89, 10623 Berlin. Currently, the only entrance is through Müller-Breslau-Straße (between "HF" and "L"; follow the signs).
Campus TUB (Click to view full PDF)
Hotels
FRICO 2026 has concluded. Hotel and travel information was as follows.
Loading this map transmits your IP address and information about your
browser and device to Google Ireland Ltd., and may involve a transfer of
that data to servers in the USA. Nothing is sent to Google until you tick
the box below. See our
privacy policy and
Google's
privacy policy.
FRICO 2026 has concluded. Thank you to all participants, speakers, and sponsors for making the workshop a success!
History of FRICO
Ulrich Pferschy described the origin of the FRICO in the program booklet of the 10th FRICO as follows:
" … However, some people who are taking part in this relaxed exchange of ideas for the first time may ask themselves how such an unstructured event came about. To prevent the formation of false legends, which are sometimes already spread in an hour with wine, I would like to briefly present the official version of the FRICO creation.
In the autumn of 1996, a two-week summer school on the approximation of combinatorial optimization problems took place in Udine (this was the summer school to which the great Papadimitriou had mistakenly arrived a year too early). On the free weekend contained therein, it was obvious to undertake an excursion into the surrounding wine country. At least this was the firm conviction of the two Graz participants, Rüdiger Rudolf and myself. Since excursions of this kind are only half as nice for two (if they are men), we successfully tried to win the apparently like-minded participants Dagmar Handke (Konstanz) and Katja Wolf (Cologne) as companions. The beautiful excursion ended in a trattoria in Cividale with a special local dish, which can best be described as a mixture of potatoes, onions, bacon, and cheese; nothing for a weak stomach. The Frico cheese, a Friulian specialty, gives the dish its name. In a cheerful circle, Katja invited all of us to a Frico dinner in Cologne without knowing what she was starting.
However, it was to take over a year before this invitation could be made more concrete. Now the way from Graz to Cologne is quite long, and as optimizers, we tried to combine the pleasant with the useful. Without further ado, we offered to combine the private visit with a lecture at the then ZPR Cologne. And so that it didn′t look as if the people of Cologne can only listen and have nothing to say themselves, Katja immediately obliged a few "locals" to give further lectures. Thus a one-day workshop had developed in the twinkling of an eye. Although the organizer said: "We can′t call it FRICO", I managed to find the acronym that is known today.
The first FRICO Workshop in 1997 was a great success (in contrast to the Frico dinner in the evening, which was canceled from the program in the following years). This moved Professor Schrader to donate a barrel of Kölsch and to "threaten" to continue organizing this event format on his own if we did not. Of course, we couldn′t afford to let that happen, and so the second FRICO was decided in Graz in 1998.
The rest is history."
