Approximation Algorithms for Embedding with Extra Information and Ordinal Relaxation
4This talk considers approximation algorithms for embedding: constructing a global geometry that is approximately consistent with a given local geometry, which is typically represented by distances between some or all pairs of points in a point set. Such problems arise, for example, in the contexts of sensor networks and structural analysis of proteins. The first half of the talk is about embedding when given more information than just distances. In many cases, such information makes it possible to design efficient algorithms that embed with approximately minimum possible distortion. One example of extra information, available in some practical scenarios, is approximate angles between pairs of edges of known distance. We give efficient approximation algorithms for embedding in this and several other cases. In particular, one type of extra information, an ``extremum oracle,'' can be guessed in quasipolynomial time, leading to the first such algorithm for embedding into 2D given only distances. This is joint work with Mihai Badoiu, MohammadTaghi Hajiaghayi, and Piotr Indyk (SoCG 2004). The second half of the talk is about relaxed ordinal embedding, where the goal is to find an embedding in which the distances do not match the specified values but have roughly the correct relative order. Although exact ordinal embeddings have been studied before, we introduce the idea of getting the correct relative order for distances that are substantially different (have a large ratio), but violate the order when distances are close, for the minimum possible value of ``close.'' The minimum possible relaxation is related to the minimum possible distortion of regular metric embeddings, and we show that in some cases these two notions differ substantially. Minimum relaxation ordinal embeddings open the door for efficient approximation algorithms where such algorithms are impossible or difficult for minimum-distortion metric embedding, and may lead to better approximation algorithms for various geometric and graph problems. This is joint work with Mihai Badoiu, Martin Farach-Colton, MohammadTaghi Hajiaghayi, and Anastasios Sidiropoulos (2004).