Conférences  >  Physique  >  Physique numérique  >  Canada

Sélecionner un pays
1
BIRS Workshop — Approximation Algorithms and the Hardness of Approximation
17 sep 2023 - 22 sep 2023 • Banff, Alberta, Canada
Organisateur:
Banff International Research Station (BIRS) for Mathematical Innovation and Discovery
Résumé:
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 conjecture that P does not equal NP. 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 does not equal 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.
Identifiant de l'évènement:
1499180


Conference-Service.com met à la disposition de ses visiteurs des listes de conférences et réunions dans le domaine scientifique. Ces listes sont publiées pour le bénéfice des personnes qui cherchent une conférence, mais aussi, bien sûr, pour celui des organisateurs. Noter que, malgré tout le soin que nous apportons à la vérification des données entrées dans nos listes, nous ne pouvons accepter de responsabilité en ce qui concerne leur exactitude ou étendue. Pensez donc à vérifier les informations présentées avec les organisateurs de la conférence ou de la réunion avant de vous engager à y participer!

Y'a pas de suivi | Y'a pas de pop-ups | Y'a pas d'animations
Dernière mise à jour: 27 juillet 2022