Finite metric spaces - The algorithmic aspect
Abstract: In the last several years there has been an intense effort to study discrete metric spaces and their embeddings. This subject can be investigated from several different angles. Thus, for example, some of the basic results come from earlier investiagtions in Banach space theory. Much of the driving force behind this recent interest in finite metric spaces comes from their role in the design of efficient algorithms.
In this talk I will try to illustrate some of the beautiful and unexpected ways in which finite metric spaces and their embeddings come into play in the creation of new algorithms. These algorithmic applications fall into two main categories: Approximation algorithms for NP-hard problems and questions related to large-scale clustering problems.