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.

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.