Workshop: Approximation and relaxation

Dates: November 15 - 19, 2021
Venue: This workshop is currently scheduled to take place online

In case there will be relaxations with regard to the hygienic restrictions that are currently necessary due to COVID-19, the workshop may take place on-site. This will be decided  approx. 3 months prior to the event and this website will be updated correspondingly.

Organizers: Fabrizio Grandoni (IDSIA, Manno), Neil Olver (London), Laura Sanità (Waterloo), 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.