- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- D-width, metric embedding, and their connections
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
D-width, metric embedding, and their connections Ali Safari, Mohammad
Abstract
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 [cursive l]₁ 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. While every metric is embeddable into [cursive l]₁ with distortion O (log n) [13], and the bound is tight [39], for special classes of metrics better bounds exist. Shortest path metrics for trees and outerplanar graphs are isometrically embeddable into [cursive l]₁ [41]. Series-parallel graphs [28] and k-outerplanar graphs [19] (for constant k) are embeddable into[cursive l]₁ with constant distortion planar graphs and bounded tree-width graphs are conjectured to have constant distortion in embedding to [cursive l]₁ . Bounded tree-width graphs are one of most general graph classes on which several hard problems are tractable. We study the embedding of series-parallel graphs (or, more generally, graphs with tree-width two) into [cursive l]₁ and also the embedding between two line metrics. We then move our attention to the generalization of tree-width to digraphs and hypergraphs and study several relevant problems.
Item Metadata
Title |
D-width, metric embedding, and their connections
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2007
|
Description |
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 [cursive l]₁ 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. While every metric is embeddable into [cursive l]₁ with distortion O (log n) [13], and the bound is tight [39], for special classes of metrics better bounds exist. Shortest path metrics for trees and outerplanar graphs are isometrically embeddable into [cursive l]₁ [41]. Series-parallel graphs [28] and k-outerplanar graphs [19] (for constant k) are embeddable into[cursive l]₁ with constant distortion planar graphs and bounded tree-width graphs are conjectured to have constant distortion in embedding to [cursive l]₁ . Bounded tree-width graphs are one of most general graph classes on which several hard problems are tractable. We study the embedding of series-parallel graphs (or, more generally, graphs with tree-width two) into [cursive l]₁ and also the embedding between two line metrics. We then move our attention to the generalization of tree-width to digraphs and hypergraphs and study several relevant problems.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2011-02-18
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
|
DOI |
10.14288/1.0052053
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Campus | |
Scholarly Level |
Graduate
|
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.