UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Diversity embeddings and the hypergraph sparsest cut Jozefiak, Adam Daniel

Abstract

Good approximations have been attained for the sparsest cut problem by rounding solutions 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 are a generalization of metric spaces in which the nonnegative function is defined on all subsets as opposed to only on pairs of elements. We show that this approach yields an O(logn)-approximation when either the supply or demands are given by a graph. This result improves upon Plotkin et al.’s O(log(kn)logn)-approximation [28], where k is the number of demands, in the setting where the supply is given by a graph and the demands are given by a hypergraph. Additionally, we provide an O(min{rG,rH}log(rH)logn)-approximation for when the supply and demands are given by hypergraphs whose hyperedges are bounded in cardinality by rG and rH respectively. To establish these results we provide an O(logn)-distortion 𝓵1 embedding for the class of diversities known as diameter diversities. This improves upon Bryant and Tupper’s O((logn)^2)-distortion embedding [31]. The smallest known distortion with which an arbitrary diversity can be embedded into 𝓵1 is O(n). We show that for any ε > 0 and any p > 0, there is a family of diversities which cannot be embedded into 𝓵1 in polynomial time with distortion smaller than O(n^(1−ε)) based on querying the diversities on sets of cardinality at most O((logn)ˆp), unless P = NP. This disproves (an algorithmic refinement) of Bryant and Tupper’s conjecture that there exists an O(√n)-distortion 𝓵1 embedding based off a diversity’s induced metric. In addition, we demonstrate via hypergraph cut sparsifiers that it is sufficient to develop a low-distortion embedding for diversities induced by sparse hypergraphs for the purpose of obtaining good approximations for the sparsest cut in hypergraphs.

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International