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.
- ISBN 13 : 9780494319208
- ISBN 10 : 0494319208
- Judul : D-width, Metric Embedding, and Their Connections
- Pengarang : Mohammad Ali Safari,
- Penerbit : ProQuest
- Bahasa : en
- Tahun : 2007
- Halaman : 113
- Halaman : 113
- Google Book : http://books.google.co.id/books?id=912Y5OCyq-AC&dq=inauthor:mohammad+ali&hl=&source=gbs_api
-
Ketersediaan :
Embedding between metric spaces is a very powerful algorithmic tool and has been used for finding good approximation algorithms for several problems.
