The 4/3 Additive Spanner Exponent Is Tight
The 4/3 Additive Spanner Exponent Is Tight
复制标题
4/3 加法扳手指数很紧
DOI：
10.1145/3088511
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Gregory Bodwin
中科院分区：
文献类型：
--
作者：
Amir Abboud;Gregory Bodwin
图是一个稀疏子图，它近似地保持了原始图的两两距离。众所周知，只要距离误差是乘性测量的，那么在稀疏性和近似质量之间存在平滑的折衷。该领域的一个中心问题是证明或反驳这种权衡是否也存在于加性误差的制度。也就是说，是否对所有n> 0，都存在一个常数k n，使得每个图在O（n1+ n）条边上都有一个n，它的两两距离保持到+k n？以前的下界与这个问题的正解决方案一致，而以前的上界展示了一个折衷曲线的开始：所有图在O（n3/2）边上有+2 spectrum，在O（n7/5）边上有+4 spectrum，在O（n4/3）边上有+6 spectrum。然而，进展在n4/3边界神秘地停止了，尽管社区做出了巨大的努力，但问题仍然对所有0 < 1/3都是开放的。我们的主要结果是一个令人惊讶的负面决议的开放问题，即使在一个高度概括的设置。我们证明了一个新的信息论不可压缩性界：没有函数可以将图压缩到O（n4/3 − n2）位，因此距离信息可以在+no（1）错误内恢复。作为我们定理的一个特例，我们得到了加性空间稀疏性的一个严格下界：O（n ~ 4/3）边上的+6阶加性空间不能在指数上得到改进，即使允许任何次多项式量的加性误差.我们的定理也暗示了相关对象的新下界;例如，O（n4/3）边缘上的20岁+4模拟器也不能在指数上改进，除非误差允许是多项式。我们构造的核心是一种新型的图积，我们称之为障碍积。直观地说，它取两个图G，H，并产生一个新的图G <$H，其最短路径结构在局部上看起来像H，但在全局上看起来像G。
A spanner is a sparse subgraph that approximately preserves the pairwise distances of the original graph. It is well known that there is a smooth tradeoff between the sparsity of a spanner and the quality of its approximation, so long as distance error is measured multiplicatively. A central open question in the field is to prove or disprove whether such a tradeoff exists also in the regime of additive error. That is, is it true that for all ϵ > 0, there is a constant kϵ such that every graph has a spanner on O(n1+ϵ) edges that preserves its pairwise distances up to +kϵ? Previous lower bounds are consistent with a positive resolution to this question, while previous upper bounds exhibit the beginning of a tradeoff curve: All graphs have +2 spanners on O(n3/2) edges, +4 spanners on Õ(n7/5) edges, and +6 spanners on O(n4/3) edges. However, progress has mysteriously halted at the n4/3 bound, and despite significant effort from the community, the question has remained open for all 0 < ϵ < 1/3. Our main result is a surprising negative resolution of the open question, even in a highly generalized setting. We show a new information theoretic incompressibility bound: There is no function that compresses graphs into O(n4/3 − ϵ) bits so distance information can be recovered within +no(1) error. As a special case of our theorem, we get a tight lower bound on the sparsity of additive spanners: the +6 spanner on O(n4/3) edges cannot be improved in the exponent, even if any subpolynomial amount of additive error is allowed. Our theorem implies new lower bounds for related objects as well; for example, the 20-year-old +4 emulator on O(n4/3) edges also cannot be improved in the exponent unless the error allowance is polynomial. Central to our construction is a new type of graph product, which we call the Obstacle Product. Intuitively, it takes two graphs G, H and produces a new graph G ⊗ H whose shortest paths structure looks locally like H but globally like G.
更好的距离保持器和附加扳手
影响因子：
1.3
作者：
Bodwin, Greg;Williams, Virginia Vassilevska
通讯作者：
Williams, Virginia Vassilevska
次线性加法扳手下界的层次结构
DOI：
10.1137/1.9781611974782.36
发表时间：
2017
期刊：
SODA 2017
影响因子：
--
作者：
Abboud, Amir;Bodwin, Greg;Pettie, Seth
通讯作者：
Pettie, Seth