Workshop: Approximation and relaxation

Dates: November 15 - 19, 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: Fabrizio Grandoni (IDSIA, Manno), Neil Olver (London), Laura Sanità (Eindhoven), Jens Vygen (Bonn)



Many of the problems of interest in combinatorial optimization are NP-hard, implying that we do not expect efficient algorithms to solve these problems exactly. This motivates the area of approximation algorithms: efficient algorithms that yield solutions that, while suboptimal, have provably good performance. The use of sophisticated convex relaxations as a tool to tame the inherent complexity of NP-hard problems is of particular interest, and lies at the heart of recent exciting successes for notorious problems such as the travelling salesman problem. This workshop aims at bringing together researchers working on approximation algorithms to build on recent progress, investigate more sophisticated ways of exploiting convex relaxations, and explore other connections such as the use of techniques from parametrized complexity.


You can find the abstract here.

You can find the schedule here.

Video recordings:

Day 1:

Nathan Klein: A (Slightly) Improved Approximation Algorithm for Metric TSP

Stefan Hougardy: The Approximation Ratio of the k-Opt Heuristic for Euclidean TSP

Karol Węgrzycki: A Gap-ETH-Tight Approximation Scheme for Euclidean TSP

Sarah Morell: Single Source Unsplittable Flows with Arc-Wise Lower and Upper Bounds

Rasmus Kyng: Two-Commodity Flow is as Hard as Linear Programming

Day 2

Jesper Nederlof: Bipartite TSP in O(1.9999n) Time, Assuming Quadratic Time Matrix Multiplication

Karthik Chandrasekaran: lp-Norm Multiway Cut

Adam Polak: Nearly-Tight and Oblivious Algorithms for Explainable Clustering

Thomas Rothvoß: Scheduling with Communication Delays via LP Hierarchies and Clustering

Jannik Matuschke: Generalized Malleable Scheduling via Discrete Convexity

Day 3

András Sebő: Geometric Packing and Hitting: Patching some Gaps for Squares

Britta Peis: A Primal-Dual Approximation Framework for Weighted Integer Covering Problems

Stephan Held: Approximating the Discrete Time-Cost Tradeoff Problem with Bounded Depth

Federico Soldá: Scalar and Matrix Chernoff Bounds from l_(inf)-independence

Day 4

Vera Traub: Recent Progress on Weighted Tree Augmentation

Afrouz Jabal Ameli: Breaching the 2-Approximation Barrier for Connectivity Augmentation

Dylan Hyatt-Denesik: Node-Connectivity Augmentation via Iterative Randomized Rounding

Matthias Mnich: Approximating Sparsest Cut in Low-Treewidth Graphs

Jarek Byrka: Online Facility Location with Linear Delay

Day 5

László Végh: Approximating Nash Social Welfare under Rado Valuations

Laura Vargas Koch: Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time

Alantha Newman: Voting Algorithms for Unique Games on Complete Graphs

Yuri Faenza: Approximating Popular and Stable Matchings