Résumé de séminaire

Résumé :

We study problems of embedding arbitrary finite metrics into a line.

In the first version, we study non-contracting embeddings that minimize average distortion. Since a path metric (or a line metric) is quite restricted, such embeddings could have high average distortions (Omega(n), where n is the number of points in the original metric). Furthermore, finding best embedding of even a tree metric into a line to minimize average distortion is NP-hard. Hence, we focus on approximating the best possible embedding for given input metric, and give a constant-factor approximation for the problem. For the case of the tree metrics as input, we present a QPTAS (Quasi-Polynomial Time Approximation Scheme), using ideas from Euclidean TSPs.

In a second version when the embedding need not necessarily be non-contracting, we consider the problem of finding an embedding of an arbitrary metric into a line to minimize the L₁ norm between the two metrics. We show this NP-hard problem admits an O(log n) approximation for n-point metrics using ideas from approximating weighted multicuts in graphs.

This talk describes joint work with Kedar Dhamdhere and Anupam Gupta, both from CMU.

Références :

Home page : http://www.gsia.cmu.edu/andrew/ravi/