Diversity Embeddings and the Hypergraph Sparsest Cut
AD Jozefiak, FB Shepherd - arXiv preprint arXiv:2303.04199, 2023 - arxiv.org
arXiv preprint arXiv:2303.04199, 2023•arxiv.org
Good approximations have been attained for the sparsest cut problem by rounding solutions
to convex relaxations via low-distortion metric embeddings. Recently, Bryant and Tupper
showed that this approach extends to the hypergraph setting by formulating a linear program
whose solutions are so-called diversities which are rounded via diversity embeddings into
$\ell_1 $. 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 …
to convex relaxations via low-distortion metric embeddings. Recently, Bryant and Tupper
showed that this approach extends to the hypergraph setting by formulating a linear program
whose solutions are so-called diversities which are rounded via diversity embeddings into
$\ell_1 $. 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 …
Good approximations have been attained for the sparsest cut problem by rounding solutions to convex relaxations via low-distortion metric embeddings. Recently, Bryant and Tupper showed that this approach extends to the hypergraph setting by formulating a linear program whose solutions are so-called diversities which are rounded via diversity embeddings into . 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 a polytime -approximation when either the supply or demands are given by a graph. This result improves upon Plotkin et al.'s -approximation, where is the number of demands, for the setting where the supply is given by a graph and the demands are given by a hypergraph. Additionally, we provide a polytime -approximation for when the supply and demands are given by hypergraphs whose hyperedges are bounded in cardinality by and respectively. To establish these results we provide an -distortion embedding for the class of diversities known as diameter diversities. This improves upon Bryant and Tupper's $O(\log\^2{n})$-distortion embedding. The smallest known distortion with which an arbitrary diversity can be embedded into is . We show that for any and any , there is a family of diversities which cannot be embedded into in polynomial time with distortion smaller than based on querying the diversities on sets of cardinality at most , unless . This disproves (an algorithmic refinement of) Bryant and Tupper's conjecture that there exists an -distortion embedding based off a diversity's induced metric.
arxiv.org