Approximation algorithms and the hardness of approximation (11w5117)

The Banff International Research Station will host the "Approximation algorithms and the hardness of approximation" workshop from November 27th to December 2nd, 2011.

Many optimization problems that arise in the sciences, engineering, and business are computationally difficult; by this we mean that that there are no known procedures to solve these problems efficiently on all inputs. Moreover, it is widely believed that no such efficient procedures exist for many of these problems.
A canonical example of such a problem is the Travelling Salesperson Problem (TSP) in which a salesperson needs to find a tour visiting every city in a given list of cities while minimizing the total distance travelled. A fruitful approach that has been followed for more than three decades is to focus on approximation algorithms. These are heuristics that guaranteed to run fast and also, for each input, give a bound on the quality of the output solution when compared to that of the best solution for that input.

In addition to the practical benefits of the heuristics that have been designed via approximation algorithms, there have been several other equally important benefits. Fundamental and important connections have been established between computer science, mathematics, engineering, economics and several other areas. As the field matures, the techniques and ideas have become much more sophisticated.
The workshop will help bring together leading as well as young researchers to discuss and exchange the recent tools and advances and tackle the major open 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).