Microsoft Research Audio 104831: Approximation Algorithms For Embedding With Extra Information And Ordinal Relaxation - Info and Reading Options

The Internet Archive:

<p>This 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.</p><p>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).</p><p>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).</p><div class="fs30">©2004 Microsoft Corporation. All rights reserved.</div>

Search for “Microsoft Research Audio 104831: Approximation Algorithms For Embedding With Extra Information And Ordinal Relaxation” downloads:

Visit our Downloads Search page to see if downloads are available.

Find “Microsoft Research Audio 104831: Approximation Algorithms For Embedding With Extra Information And Ordinal Relaxation” in Libraries Near You:

Read or borrow “Microsoft Research Audio 104831: Approximation Algorithms For Embedding With Extra Information And Ordinal Relaxation” from your local library.

• The WorldCat Libraries Catalog: Find a copy of “Microsoft Research Audio 104831: Approximation Algorithms For Embedding With Extra Information And Ordinal Relaxation” at a library near you.