A Hierarchy of Lower Bounds for Sublinear Additive Spanners
A Hierarchy of Lower Bounds for Sublinear Additive Spanners
复制标题
次线性加法扳手下界的层次结构
DOI：
10.1137/1.9781611974782.36
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Pettie, Seth
中科院分区：
文献类型：
--
作者：
Abboud, Amir;Bodwin, Greg;Pettie, Seth
Spanner、模拟器和近似距离预言机可以被视为有损压缩方案，它们表示小空间中的未加权图形度量，saybits。 压缩方案的稀疏参数和拉伸函数之间存在固有的权衡，但这种权衡的定性本质仍然是一个持续存在的开放问题。人们早就知道，当存在具有恒定加性拉伸（距离拉伸到最大）的方案时，Abboud 和 Bodwin 最近的结果表明，当不存在这样的方案时。因此，为了获得实际有效的图形压缩，我们必须支付超常数附加拉伸，但我们究竟需要支付多少？在本文中，我们证明 Abboud 和 Bodwin 的下界只是下界层次结构的第一步，它表征了稀疏参数的最优拉伸函数的渐近行为。具体来说，对于任何整数，任何使用位的压缩方案都具有亚线性加性拉伸函数：该下限与 Thorup 和 Zwick (2006) 的次线性加性仿真器构造相匹配。它还表明，Elkin 和 Peleg 扳手在 、 和 之间具有本质上最佳的权衡，并且 Pettie (2009) 和 Chechik (2013) 的次线性加性扳手与最佳值相差不远。为了补充这些下限，我们提出了一种新的扳手结构，其尺寸为，其中。这个尺寸界限改进了 Elkin 和 Peleg (2004)、Thorup 和 Zwick (2006) 以及 Pettie (2009) 的扳手。根据我们的下限，尺寸和拉伸功能都无法得到实质性改善。我们的下界技术在阿布德和博德温的框架中展示了几个有趣的自由度。通过仔细利用这些自由度，我们能够获得几个相关组合对象的下界。我们得到了跳集大小的下界，与 Elkin 和 Neiman 的构造（2016）相匹配，以及保留传递闭包的有向图的快捷集的下界。 我们的下界简化了 Hesse (2003) 对 Thorup 猜想 (1992) 的反驳，Thorup 猜想指出添加线性数量的捷径足以将直径减小到多对数。最后，我们展示了图压缩方案的匹配上限和下限，该方案至少适用于具有周长的图度量。结果之一是 Baswana 等人 (2010) 的加法扳手尺寸无法在指数上得到改进。
Spanners, emulators, and approximate distance oracles can be viewed aslossycompression schemes that represent an unweighted graph metric in small space, saybits. There is an inherent tradeoff between the sparsity parameterand thestretch functionof the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem. It has been known for some time that whenthere are schemes with constantadditivestretch (distanceis stretched to at most), and recent results of Abboud and Bodwin show that whenthere are no such schemes. Thus, to get practically efficient graph compression withwe must pay superconstant additive stretch, but exactly how much do we have to pay? In this paper we show that the lower bound of Abboud and Bodwin is just the first step in ahierarchyof lower bounds that characterize the asymptotic behavior of the optimal stretch functionfor sparsity parameter. Specifically, for any integer, any compression scheme usingbits has asublinear additive stretchfunction:. This lower bound matches Thorup and Zwick's (2006) construction of sublinear additiveemulators. It also shows that Elkin and Peleg's-spanners have an essentially optimal tradeoff between,, and, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal. To complement these lower bounds we present a new construction of-spanners with size, where. This size bound improves on the spanners of Elkin and Peleg (2004), Thorup and Zwick (2006), and Pettie (2009). According to our lower bounds neither the size nor stretch function can be substantially improved. Our lower bound technique exhibits several interesting degrees of freedom in the framework of Abboud and Bodwin. By carefully exploiting these freedoms, we are able to obtain lower bounds for several related combinatorial objects. We get lower bounds on the size of-hopsets, matching Elkin and Neiman's construction (2016), and lower bounds onshortcutting setsfor digraphs that preserve the transitive closure. Our lower bound simplifies Hesse's (2003) refutation of Thorup's conjecture (1992), which stated that adding a linear number of shortcuts suffices to reduce the diameter to polylogarithmic. Finally, we show matching upper and lower bounds for graph compression schemes that work for graph metrics with girth at least. One consequence is that Baswana et al.'s (2010) additive-spanners with sizecannot be improved in the exponent.
登录
查看更多内容
新型增材扳手
DOI：
--
发表时间：
2013
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
S. Chechik
通讯作者：
S. Chechik
DOI：
10.1006/jagm.1996.0829
发表时间：
1997
期刊：
J. Algorithms
影响因子：
--
作者：
M. Thorup
通讯作者：
M. Thorup
DOI：
10.1006/jagm.1997.0888
发表时间：
1997
期刊：
J. Algorithms
影响因子：
--
作者：
P. Klein;Sairam Subramanian
通讯作者：
Sairam Subramanian
通过保留复杂性的映射在自由树上进行计算
影响因子：
1.1
作者：
B. Chazelle
通讯作者：
B. Chazelle
DOI：
--
发表时间：
2005
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
L. Roditty;M. Thorup;Uri Zwick
通讯作者：
Uri Zwick