Loading...
Please wait, while we are loading the content...
Similar Documents
Low-distortion embeddings of general metrics into the.
| Content Provider | CiteSeerX |
|---|---|
| Author | Bădoiu, Mihai Chuzhoy, Julia Indyk, Piotr Sidiropoulos, Anastasios |
| Abstract | A low-distortion embedding between two metric spaces is a mapping which preserves the distances between each pair of points, up to a small factor called distortion. Low-distortion embeddings have recently found numerous applications in computer science. Most of the known embedding results are ”absolute”, that is, of the form: any metric Y from a given class of metrics C can be embedded into a metric X with low distortion c. This is beneficial if one can guarantee low distortion for all metrics Y in C. However, in many situations, the worstcase distortion is too large to be meaningful. For example, if X is a line metric, then even very simple metrics (an n-point star or an n-point cycle) are embeddable into X only with distortion linear in n. Nevertheless, embeddings into the line (or into low-dimensional spaces) are important for many applications. A solution to this issue is to consider ”relative ” (or ”approximation”) embedding problems, where the goal is to design an (a-approximation) algorithm which, given any metric X from C as an input, finds an embedding of X into Y which has distortion a ∗ cY (X), where cY (X) is the best possible distortion of an embedding of X into Y. In this paper we show algorithms and hardness results for relative embedding problems. In particular we give: • an algorithm that, given a general metric M, finds an embedding with distortion O( ∆ 3/4 poly(cline(M))), where ∆ is the spread of M • an algorithm that, given a weighted tree metric M, finds an embedding with distortion poly(cline(M)) • a hardness result, showing that computing minimum line distortion is hard to approximate up to a factor |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Low-distortion Embeddings General Metric Low Distortion Hardness Result Many Application Numerous Application Simple Metric Possible Distortion Computer Science N-point Star Metric Space Many Situation Worstcase Distortion Relative Embedding Problem Embedding Result Weighted Tree Metric Distortion Linear Distortion Poly Small Factor Low-dimensional Space Minimum Line Distortion N-point Cycle |
| Content Type | Text |
| Resource Type | Article |
