Sebanyak 1 item atau buku ditemukan

D-width, Metric Embedding, and Their Connections

Embedding between metric spaces is a very powerful algorithmic tool and has been used for finding good approximation algorithms for several problems. In particular, embedding to an ℓ1 norm has been used as the key step in an approximation algorithm for the sparsest cut problem. The sparsest cut problem, in turn, is the main ingredient of many algorithms that have a divide and conquer nature and are used in various fields.

Embedding between metric spaces is a very powerful algorithmic tool and has been used for finding good approximation algorithms for several problems.