Approximation Algorithms and Parameterized Complexity

The Banff International Research Station will host the "Approximation Algorithms and Parameterized Complexity" workshop from November 29th to December 4th, 2015.

NP-hard problems are optimization problems that are notoriously difficult to solve. They are in fact so difficult that the only known solutions for them require impractically large amounts of time even on the fastest existing computers. There are thousands of these problems arising from a very rich and varied number of applications.

Two approaches that have been independently, but very successfully used to deal with NP-hard problems are approximation algorithms and parameterized algorithms. Approximation algorithms are efficient methods which do not necessarily find optimum solutions; yet, they do guarantee that the output solution achieves a bounded ratio to the optimum. Parameterized algorithms identify and exploit properties of a problem that make it hard to solve to produce efficient solutions for many instances. This workshop will explore relationships between techniques used in the design of approximation and parameterized algorithms to gain a better understanding of what makes a problem difficult to solve, with the aim of developing better tools for tackling NP-hard problems.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides 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 is located at The Banff Centre in Alberta and 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).

BIRS Scientific Director, Nassif Ghoussoub
E-mail: birs-director[@]birs.ca
http://www.birs.ca/~nassif