| LDR | | 00000nam u2200205 4500 |
| 001 | | 000000435242 |
| 005 | | 20200227165025 |
| 008 | | 200131s2019 ||||||||||||||||| ||eng d |
| 020 | |
▼a 9781687977564 |
| 035 | |
▼a (MiAaPQ)AAI27603052 |
| 035 | |
▼a (MiAaPQ)OhioLINKosu1555337435997622 |
| 040 | |
▼a MiAaPQ
▼c MiAaPQ
▼d 247004 |
| 082 | 0 |
▼a 004 |
| 100 | 1 |
▼a Carpenter, Timothy. |
| 245 | 10 |
▼a Algorithms For Low-Distortion Embeddings Into Geometrically Restricted Spaces. |
| 260 | |
▼a [S.l.]:
▼b The Ohio State University.,
▼c 2019. |
| 260 | 1 |
▼a Ann Arbor:
▼b ProQuest Dissertations & Theses,
▼c 2019. |
| 300 | |
▼a 149 p. |
| 500 | |
▼a Source: Dissertations Abstracts International, Volume: 81-06, Section: B. |
| 500 | |
▼a Advisor: Sidiropoulos, Anastasios |
| 502 | 1 |
▼a Thesis (Ph.D.)--The Ohio State University, 2019. |
| 506 | |
▼a This item must not be sold to any third party vendors. |
| 520 | |
▼a 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. |
| 590 | |
▼a School code: 0168. |
| 650 | 4 |
▼a Mathematics. |
| 650 | 4 |
▼a Computer science. |
| 690 | |
▼a 0984 |
| 690 | |
▼a 0405 |
| 710 | 20 |
▼a The Ohio State University.
▼b Computer Science and Engineering. |
| 773 | 0 |
▼t Dissertations Abstracts International
▼g 81-06B. |
| 773 | |
▼t Dissertation Abstract International |
| 790 | |
▼a 0168 |
| 791 | |
▼a Ph.D. |
| 792 | |
▼a 2019 |
| 793 | |
▼a English |
| 856 | 40 |
▼u http://www.riss.kr/pdu/ddodLink.do?id=T15494582
▼n KERIS
▼z 이 자료의 원문은 한국교육학술정보원에서 제공합니다. |
| 980 | |
▼a 202002
▼f 2020 |
| 990 | |
▼a ***1008102 |
| 991 | |
▼a E-BOOK |