Workshop: Parametrized complexity and discrete optimization

Dates: December 6 - 10, 2021
Venue: HIM lecture hall, Poppelsdorfer Allee 45, Bonn

Due to COVID-19, participation must be coupled with proof that each participant is either fully vaccinated, cured or tested negative on COVID. This procedure corresponds to the current hygienic regulations. Participation can therefore only be allowed to registered participants, who will be informed about the corresponding on-site procedure in due time.

The workshop will be held as a hybrid event. The lectures given during the workshop will be recorded by default.

Organizers: Parinya Chalermsook (Aalto), Friedrich Eisenbrand (Lausanne), Fedor Fomin (Bergen), Jesper Nederlof (Utrecht)


This Workshop focuses on the synergy between parametrized complexity and discrete optimization, two active and vibrant areas of mathematics and computer science. On the one hand, a fine-grained/parametrized view of discrete optimization has recently led to groundbreaking results (e.g. the role of fine-grained complexity assumptions, such as ETH and SETH, in explaining the lack of progress on long-standing open problems in discrete optimization) as well as new directions of research (e.g. parametrized approximation algorithms). On the other hand, techniques from Discrete Optimization, such as integer programming and the algorithmic geometry of numbers, as well as convex programming, are becoming indispensable tools in modern parameterized complexity that leads to exciting new results.

The goal of this workshop is to further enhance this synergy by bringing together the leading experts in these two areas.


You can find the abstract here.

You can find the schedule here.

Video Recordings:

Day 1:

Daniel Dadush: Integer Programming and the Kannan-Lovasz Conjecture

Stefan Weltge: Lattice-free simplices with lattice width 2d - o(d)

Daniel Kral: Parameterized approach to block structured integer programs

Michal Pilipczuk: Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

Samuel Fiorini: Integer programs with bounded subdeterminants and two nonzeros per row

Day 2

Saket Saurabh: Parameterized Algorithms and (Possible) Future Directions

Petr Golovach: Longest cycle above Paul Erdős-Gallai bound

Hans Bodlaender: Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space

Carla Groenland: Tight bounds for counting colourings parameterised by cutwidth via matrix ranks

Day 3

Karl Bringmann: Pseudopolynomial-time Algorithms for Optimization Problems

Kim Manuel Klein: On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius Problem

Adam Polak: Knapsack and Subset Sum with Small Items

Sorrachai Yingchareonthawornchai: Vertex Connectivity in Poly-logarithmic Max-flows

Sally Dong: A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth

Day 4

Robert Weismantel: Mixed Integer Optimization in high dimensions

Klaus Jansen: New Algorithmic Results for Bin Packing and Scheduling

Lars Rohwedder: Flow Time Scheduling and Prefix Beck-Fiala

Céline Swennenhuis: A Faster Exponential Time Algorithm for Bin Packing With Constant Bin Number

Marcin Pilipczuk: Directed flow-augmentation

Andreas Feldmann: The Parameterized Complexity of the Survivable Network Design Problem

Day 5

Karthik C. S.: Recent Hardness of Approximation results in Parameterized Complexity

Tuukka Korhonen: Fast FPT-Approximation of Branchwidth

Jana Cslovjecsek: Efficient algorithms for multistage stochastic integer programming using proximity