상세정보
Export to Refworks부가기능
Algorithms For Low-Distortion Embeddings Into Geometrically Restricted Spaces
상세 프로파일
| 자료유형 | 학위논문 |
|---|---|
| 서명/저자사항 | Algorithms For Low-Distortion Embeddings Into Geometrically Restricted Spaces. |
| 개인저자 | Carpenter, Timothy. |
| 단체저자명 | The Ohio State University. Computer Science and Engineering. |
| 발행사항 | [S.l.]: The Ohio State University., 2019. |
| 발행사항 | Ann Arbor: ProQuest Dissertations & Theses, 2019. |
| 형태사항 | 149 p. |
| 기본자료 저록 | Dissertations Abstracts International 81-06B. Dissertation Abstract International |
| ISBN | 9781687977564 |
| 학위논문주기 | Thesis (Ph.D.)--The Ohio State University, 2019. |
| 일반주기 |
Source: Dissertations Abstracts International, Volume: 81-06, Section: B.
Advisor: Sidiropoulos, Anastasios |
| 이용제한사항 | This item must not be sold to any third party vendors. |
| 요약 | We study the problem of finding a minimum-distortion embedding of the shortest path metric of a weighted or unweighted graph into a "simpler" metric X. Computing such an embedding (exactly or approximately) is a non-trivial task even when X is the metric induced by a path, or, equivalently, the real line.Embeddings of various metric spaces are frequently used in the design of algorithms, and a large literature has been developed around this study. Embeddings into 1- and 2-dimensional spaces can provide a natural abstraction of visualization tasks. Low-distortion embeddings into low-dimensional spaces can be used as a sparse representation of a data set, and embeddings into topologically restricted spaces can reveal interesting structures in a data set.In general, unless P=NP many embedding problems cannot have algorithms which run in polynomial time. We work around this by finding approximation and fixed-parameter tractable (FPT) algorithms for minimum distortion embeddings of the shortest path metric of a graph G into the shortest path metric of a subdivision of some fixed graph H, or, equivalently, into any fixed 1-dimensional simplicial complex. More precisely, we study the following problem: For given graphs G, H and integer c, is it possible to embed G with distortion c into a graph homeomorphic to H? Under this formulation, embedding into the line is the special case H=K2, and embedding into the cycle is the case H=K3, where Kk denotes the complete graph on k vertices.For this problem we give an approximation algorithm on unweighted G, which in time f(H) 쨌 poly(n), for some function f, either correctly decides that there is no embedding of G with distortion c into any graph homeomorphic to H, or finds an embedding with distortion poly(c). For the case of embedding into a cycle, we find a O(c4)-embedding of G in time O(cn3). We also give an exact FPT algorithm on G with maximum edge weight W, which in time f'(H, c, W) 쨌 poly(n), for some function f', either correctly decides that there is no embedding of G with distortion c into any graph homeomorphic to H, or finds an embedding with distortion c. For the case of embedding into a cycle, we find the embedding in time n4 cO(cW).Prior to our work, poly(OPT)-approximation or FPT algorithms were known only for embedding into paths and trees of bounded degrees. |
| 일반주제명 | Mathematics. Computer science. |
| 언어 | 영어 |
| 바로가기 | 
: 이 자료의 원문은 한국교육학술정보원에서 제공합니다. |
