Diversity Embeddings and the Hypergraph Sparsest Cut
share
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 ℓ_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 approach yields a polytime 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, where k 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 O(min{r_G,r_H}logr_Hlogn)-approximation for when the supply and demands are given by hypergraphs whose hyperedges are bounded in cardinality by r_G and r_H 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(log2̂n)-distortion embedding. 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(log^pn), 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.
READ FULL TEXT