A sparsest cut on a finite vertex set with nonnegative pair capacities and nonnegative pair demands is a partition into two nonempty parts minimizing the crossing capacity divided by the separated demand. Uniform sparsest cut is the special case in which every pair of distinct vertices has demand one. For an integer and vertex set , let assign arbitrary symmetric nonnegative capacities to unordered pairs of distinct vertices. The uniform sparsest-cut optimum is . A negative-type semimetric on a finite set is a function satisfying all triangle inequalities for which there exist vectors () in a real Hilbert space with for all , permitting zero distance between distinct points. The Goemans-Linial relaxation is . When , the integrality gap of is . The central question is how large this integrality gap can be as a function of .
Linial, London, and Rabinovich established the metric correspondence between cuts and finite embeddings. Rabinovich (2003) and Rabinovich (2008) developed the average-distortion framework connecting uniform sparsest cut to the average distance preserved by maps into that do not increase pairwise distances. For uniform sparsest cut, Arora, Rao, and Vazirani gave an approximation. Devanur, Khot, Saket, and Vishnoi proved an integrality gap for uniform sparsest cut. Kane and Meka subsequently improved this integrality-gap bound to . For arbitrary demands, the Goemans-Linial conjecture predicted a constant integrality gap. Khot and Vishnoi disproved this conjecture. Lee and Naor, Cheeger and Kleiner, Cheeger, Kleiner, and Naor (2009), and Cheeger, Kleiner, and Naor (2011) developed a geometric line of work. Naor and Young obtained the sharp general-demand lower bound. Chang, Naor, and Ren proved the matching upper bound.
The preprint proves that there exist an absolute constant and uniform sparsest-cut capacity instances on vertices with such that for all sufficiently large .
The Lean library SparsestCut formalizes this uniform sparsest-cut integrality-gap bound and its supporting results. OpenAI catalog entry 117 also lists a companion preprint on constant-factor hardness of uniform sparsest cut, which is not covered here, as the Lean library formalizes only the results of the preprint on uniform sparsest-cut integrality gaps. The results on these pages are the Lean library’s, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every result of the Lean library, so the Lean library is the reference. Where the preprint states a result differently, the statement on the page is the Lean library’s, with the preprint’s given beside it. The preprint is a guide only, giving the results their order and their names.
SparsestCut is a Lean library: 16 items, in six groups. Each has a page written by OctoInform, listed below.
No item matches.