Approximation Algorithms and Parameterized Complexity (15w5118)

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).