Back to search

University of British Columbia

Diversity embeddings and the hypergraph sparsest cut

Abstract

dc:description

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.

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

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Jozefiak, Adam Daniel. Diversity embeddings and the hypergraph sparsest cut. master's thesis, University of British Columbia, 2022. http://hdl.handle.net/2429/82677