Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 9 of 9 for “"Metric embeddings"”.

  1. Applications of Metric Embeddings in Solving Combinatorial Problems

    Metric embeddings constitute one of the fundamental tools for exploiting the underlying geometric structure of many combinatorial problems. In this dissertation we study some of the applications of metric embeddings in the field of computer science and resolve some of the previously open questions …

    washington Repository record for Applications of Metric Embeddings in Solving Combinatorial Problems (opens in a new tab)

  2. Advancements in Combinatorial Optimization and Spectral Graph Theory: Approaches to Permanents, Metric Embeddings, and Geometric Graphs

    … First, I will cover my results on planar and geometric graphs. Namely, in the papers ``On planar graphs of uniform polynomial growth'' and ``Non-existence of annular separators in geometric graphs'' we resolve several conjectures and open problems about spectral properties of a certain family of …

    washington Repository record for Advancements in Combinatorial Optimization and Spectral Graph Theory: Approaches to Permanents, Metric Embeddings, and Geometric Graphs (opens in a new tab)

  3. Probabilistic Separation and Fairness in Graph Partitioning and Assignment

    … support these results by advancing the theory of metric embeddings, presenting new approximation algorithms for embedding general metrics into hierarchically separated trees. We then apply this framework to political redistricting and show that for grid graphs, widely-used sampling methods satisfy …

    duke Repository record for Probabilistic Separation and Fairness in Graph Partitioning and Assignment (opens in a new tab)

  4. Diversity embeddings and the hypergraph sparsest cut

    … to convex relaxations via low-distortion metric embeddings [5, 24]. Recently, Bryant and Tupper showed that this approach extends to the hypergraph setting by formulating a linear program whose solutions are diversities which are rounded via diversity embeddings into 𝓵1 [31]. Diversities …

    ubc Repository record for Diversity embeddings and the hypergraph sparsest cut (opens in a new tab) Download PDF for Diversity embeddings and the hypergraph sparsest cut (opens in a new tab)

  5. The complexity of expansion problems

    … to error correcting codes, sampling algorithms, metric embeddings, among others, and to practitioners, as algorithms for graph partitioning can be used as fundamental building blocks in many applications. One of the central problems studied in this field is the sparsest cut problem, where we want …

    gatech Repository record for The complexity of expansion problems (opens in a new tab)

  6. Layering principles for wireless networks

    … particular the Lovasz extension, and the use of metric embeddings into the real line with low average distortion. In order to translate these results from polymatroidal networks to wireless networks, we propose a natural layered architecture in which information-theoretic schemes are employed at …

    uiuc Repository record for Layering principles for wireless networks (opens in a new tab)

  7. Geometric inequalities and advances in the Ribe program

    In Chapter 1 we show that not every metric space embeds coarsely into an Alexandrov space of nonpositive curvature, thus answering a question of Gromov (1993). In Chapter 2 we introduce a metric invariant called diamond convexity and show that a Banach space X has diamond convexity q if and only if …

    greece Repository record for Geometric inequalities and advances in the Ribe program (opens in a new tab)