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