Approximation Algorithms and the Hardness of Approximation (Cancelled) (20w5184)

The Casa Matemática Oaxaca (CMO) will host the "Approximation Algorithms and the Hardness of Approximation" workshop in Oaxaca, from September 20 to September 25, 2020.

Most of the many discrete optimization problems arising in the sciences, engineering, and mathematics are NP-hard, that is, there exist no efficient algorithms to solve them to optimality, assuming the P.not.=NP conjecture. The area of approximation algorithms focuses on the design and analysis of efficient algorithms that find solutions that are within a guaranteed factor of the optimal one. Loosely speaking, in the context of studying algorithmic problems, an approximation guarantee captures the quality of an algorithm -- for every possible set of input data for the problem, the algorithm finds a solution whose cost is within this factor of the optimal cost. A hardness threshold indicates the difficulty of the algorithmic problem -- no efficient algorithm can achieve an approximation guarantee better than the hardness threshold assuming that P.not.=NP. Over the last two decades, there have been major advances on the design and analysis of approximation algorithms, and on the complementary topic of the hardness of approximation.

The goal of the workshop is to focus on a few key topics that could lead to deep new results in the areas of approximation algorithms, combinatorial optimization, hardness of approximation, and proof complexity. Some of the focus topics are:
- the Traveling Salesman Problem (TSP),
- the Unique Games Conjecture,
- and Clustering and Facility Location Problems.

The Casa Matemática Oaxaca (CMO) in Mexico, and the Banff International Research Station for Mathematical Innovation and Discovery (BIRS) in Banff, are collaborative Canada-US-Mexico ventures that provide an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station in Banff is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT). The research station in Oaxaca is funded by CONACYT