Approximation algorithms and parameterized algorithms are two of the central ways to cope with computationally hard optimization problems. Yet many basic problems resist both: polynomial-time algorithms achieve only limited approximation guarantees, while exact algorithms are unlikely to be fixed-parameter tractable under natural parameters.

The goal of this Dagstuhl Seminar is to bring together researchers from approximation algorithms, parameterized complexity, computational geometry, graph algorithms, and combinatorial optimization.

We plan to investigate ideas that can cross the boundary between the approximation and parameterized communities. Topics include approximate kernelization, dynamic programming on structural decompositions, parameter-aware branching and local search, LP/SDP rounding and primal-dual methods, metric embeddings, separators, coresets, and geometric decompositions.

Our plan is to also investigates these problems from the lower bounds perspective. We will investigate reductions that simultaneously control a structural parameter and preserve an approximation gap, including approaches based on ETH, SETH, W[1], or W[2], and connections to fine-grained complexity.

The seminar is designed around collaboration rather than a sequence of long talks. Participants will form small working groups, complemented by short presentations from junior researchers and midweek and final progress reports. We hope to leave Dagstuhl with a shared map of the field, a prioritized set of open problems, concrete initial results, and new collaborations across communities that rarely meet. By combining algorithm design with lower-bound expertise, and graph structure with geometric and metric viewpoints, the seminar aims to establish parameterized approximability as a coherent research program and to open ambitious directions for the years ahead.

Creative Commons BY 4.0

Sujoy Bhore, Dániel Marx, Joseph S. B. Mitchell, Nicole Wein, and Karol Wegrzycki

This seminar qualifies for Dagstuhl's LZI Junior Researchers program. Schloss Dagstuhl wishes to enable the participation of junior scientists with a specialisation fitting for this Dagstuhl Seminar, even if they are not on the radar of the organizers. Applications by outstanding junior scientists are possible until October 30, 2026.