The integrality gap of the Goemans-Linial SDP relaxation for Sparsest Cut is at least a constant multiple of √ log n
The integrality gap of the Goemans-Linial SDP relaxation for Sparsest Cut is at least a constant multiple of √ log n
复制标题
Sparsest Cut 的 Goemans-Linial SDP 松弛的完整性差距至少是 �log n 的常数倍
DOI：
10.1145/3055399.3055413
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Young, Robert
中科院分区：
文献类型：
--
作者：
Naor, Assaf;Young, Robert
我们证明了稀疏割问题的 Goemans-Linial 半定规划松弛的完整性差距在有 n 个顶点的输入上为 Ω(√logn)，从而将先前已知的上限 (logn)1/2+o(1) 与低阶因子相匹配。该陈述是以下新的等周型不等式的结果。考虑 8 正则图，其顶点集是 5 维整数网格 ℤ5，其中每个顶点 (a,b,c,d,e)ε ℤ5 连接到 8 个顶点 (a± 1,b,c,d,e), (a,b± 1,c,d,e), (a,b,c± 1,d,e±a), (a,b,c,d± 1,e±b)。该图称为 5 维离散海森堡群的凯莱图。给定 Ω⊆ ℤ5，用 |∂hΩ| 表示该图中其边缘边界的大小（也称为 Ω 的水平周长）。 Fortϵ ℕ，表示为 |∂vtΩ| (a,b,c,d,e)ϵ ℤ5 的数量使得两个向量 (a,b,c,d,e),(a,b,c,d,e+t) 中的一个正好在 Ω 中。 Ω 的垂直周长定义为 |∂vΩ|= √Σt=1∞|∂vtΩ|2/t2。我们证明每个子集 Ω⊆ ℤ5 满足 |∂vΩ|=O(|∂hΩ|)。这种垂直与水平的等周不等式产生了上述稀疏割的完整性差距，并回答了几个独立感兴趣的几何和分析问题。上述定理是一个程序的顶峰，该程序的目的是通过海森堡群的可嵌入性属性来理解 Goemans-Linial 半定程序的性能。这些研究具有数学意义，甚至超出了它们与近似算法和组合优化的既定相关性。特别是，它们对一系列数学学科做出了贡献，包括泛函分析、几何群论、调和分析、亚黎曼几何、几何测度论、遍历理论、群表示和度量微分。本文建立在上述引用的著作的基础上，但“扭曲”的是，虽然这些著作对于任何有限维海森堡群同样有效，但我们的结果对于 5 维（或更高）的海森堡群成立，但对于 3 维海森堡群则失败。这一见解引出了我们的核心贡献，即从 ℝ3 上相应奇异积分的（局部）L2 有界性推导出 ℝ5 上某个奇异积分的端点 L1 有界性。为此，我们本着 David 和 Semmes 在 ℝn 中进行的构造的精神，设计了海森堡群子集的电晕型分解，但有两个主要概念差异（除了由于海森堡群几何特性而产生的更多技术差异）。首先，我们分解的“原子”是 Franchi、Serapioni 和 Serra Cassano 意义上的内在 Lipschitz 图的扰动（加上满足 Carleson 堆积条件的必要“野生”区域）。其次，我们通过使用定量单调性而不是琼斯型 β 数来控制电晕分解的局部重叠。
We prove that the integrality gap of the Goemans-Linial semidefinite programming relaxation for the Sparsest Cut Problem is Ω(√logn) on inputs withnvertices, thus matching the previously best known upper bound (logn)1/2+o(1)up to lower-order factors. This statement is a consequence of the following new isoperimetric-type inequality. Consider the 8-regular graph whose vertex set is the 5-dimensional integer grid ℤ5and where each vertex (a,b,c,d,e)∈ ℤ5is connected to the 8 vertices (a± 1,b,c,d,e), (a,b± 1,c,d,e), (a,b,c± 1,d,e±a), (a,b,c,d± 1,e±b). This graph is known as the Cayley graph of the 5-dimensional discrete Heisenberg group. Given Ω⊆ ℤ5, denote the size of its edge boundary in this graph (a.k.a. thehorizontal perimeterof Ω) by |∂hΩ|. Fortϵ ℕ, denote by |∂vtΩ| the number of (a,b,c,d,e)ϵ ℤ5such that exactly one of the two vectors (a,b,c,d,e),(a,b,c,d,e+t) is in Ω. Thevertical perimeterof Ω is defined to be |∂vΩ|= √Σt=1∞|∂vtΩ|2/t2. We show that every subset Ω⊆ ℤ5satisfies |∂vΩ|=O(|∂hΩ|). Thisvertical-versus-horizontal isoperimetric inequalityyields the above-stated integrality gap for Sparsest Cut and answers several geometric and analytic questions of independent interest.The theorem stated above is the culmination of a program whose aim is to understand the performance of the Goemans-Linial semidefinite program through the embeddability properties of Heisenberg groups. These investigations have mathematical significance even beyond their established relevance to approximation algorithms and combinatorial optimization. In particular they contribute to a range of mathematical disciplines including functional analysis, geometric group theory, harmonic analysis, sub-Riemannian geometry, geometric measure theory, ergodic theory, group representations, and metric differentiation. This article builds on the above cited works, with the "twist" that while those works were equally valid for any finite dimensional Heisenberg group, our result holds for the Heisenberg group of dimension 5 (or higher) butfailsfor the 3-dimensional Heisenberg group. This insight leads to our core contribution, which is a deduction of an endpointL1-boundedness of a certain singular integral on ℝ5from the (local)L2-boundedness of the corresponding singular integral on ℝ3. To do this, we devise a corona-type decomposition of subsets of a Heisenberg group, in the spirit of the construction that David and Semmes performed in ℝn, but with two main conceptual differences (in addition to more technical differences that arise from the peculiarities of the geometry of Heisenberg group). Firstly, the "atoms" of our decomposition are perturbations ofintrinsic Lipschitz graphsin the sense of Franchi, Serapioni, and Serra Cassano (plus the requisite "wild" regions that satisfy a Carleson packing condition). Secondly, we control the local overlap of our corona decomposition by using quantitative monotonicity rather than Jones-type β-numbers.