Finite metric spaces: combinatorics, geometry and algorithms

ABSTRACT

In the last several years a number of very interesting results were proved about finite metric spaces. Some of this work is motivated by practical considerations: Large data sets (coming e.g. from computational molecular biology, brain research or data mining) can be viewed as large metric spaces that should be analyzed (e.g. correctly clustered).On the other hand, these investigations connect to some classical areas of geometry - the asymptotic theory of finite-dimensional normed spaces and differential geometry. Finally, the metric theory of finite graphs has proved very useful in the study of graphs per se and the design of approximation algorithms for hard computational problems. In this talk I will try to explain some of the results and review some of the emerging new connections and the many fascinating open problems in this area.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory