# Jerusalem Mathematics Colloquium

á"ñùú ,øééàá
'å ,éùéîç
íåé

Thursday, 18th April 2002, 4:00 pm

Mathematics Building, Lecture Hall 2

##

Nati Linial

(Hebrew University)

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.

Coffee, Cookies at the faculty lounge at 3:30.

List of talks, 2001-02

List of talks, 2000-01

List of talks, 1998-99

List of talks, 1997-98