Search a Conference through our dedicated search page

Workshop — Approximation Algorithms and the Hardness of Approximation

20th September 2020   -   25th September 2020
Oaxaca, Mexico
https://www.birs.ca/events/2020/5-day-workshops/20w5184
Save

Abstract

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.