Abstract
dc:descriptionGood 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.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2022
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Jozefiak, Adam Daniel
- Contributors dc:contributor
-
- Shepherd, F. Bruce (Frederick Bruce)
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivatives 4.0 International
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/82677