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)
Description:
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