Open Collections

Jozefiak, Adam Daniel

University of British Columbia

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.

Text

2022-09-06

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/82677

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/