Lasserre Integrality Gaps for Graph Spanners and Related Problems
Lasserre Integrality Gaps for Graph Spanners and Related Problems
复制标题
图 Spanner 的 Lasserre 完整性差距及相关问题
DOI：
10.1007/978-3-030-80879-2_7
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Zhang, Zeyu
中科院分区：
文献类型：
--
作者：
Dinitz, Michael;Nazari, Yasamin;Zhang, Zeyu
近似图扳手的算法最近取得了重大进展，即近似给定输入图的最佳扳手的算法。本质上，所有这些算法都使用相同的基本 LP 松弛，因此各种论文研究了这种方法的局限性，并证明了该 LP 的完整性差距。我们扩展了这些结果，表明即使是最强大的提升和投影方法也无法提供显着帮助，即使对于有向和无向扳手问题，即使对于拉塞尔层次结构的级别，也证明了多项式完整性差距。我们还将这些完整性差距扩展到相关问题，特别是定向斯坦纳网络和浅光斯坦纳网络。
There has been significant recent progress on algorithms for approximating graph spanners, i.e., algorithms which approximate the best spanner for a given input graph. Essentially all of these algorithms use the same basic LP relaxation, so a variety of papers have studied the limitations of this approach and proved integrality gaps for this LP. We extend these results by showing that even the strongest lift-and-project methods cannot help significantly, by proving polynomial integrality gaps even forlevels of the Lasserre hierarchy, for both the directed and undirected spanner problems. We also extend these integrality gaps to related problems, notablyDirected Steiner NetworkandShallow-Light Steiner Network.
登录
查看更多内容
独特游戏的近乎最佳算法
DOI：
10.1145/1132516.1132547
发表时间：
2006
期刊：
Math. Oper. Res.
影响因子：
--
作者：
M. Charikar;K. Makarychev;Yury Makarychev
通讯作者：
Yury Makarychev
通过全局相关性舍入半定编程层次结构
DOI：
10.1109/focs.2011.95
发表时间：
2011
期刊：
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
B. Barak;P. Raghavendra;David Steurer
通讯作者：
David Steurer
传递闭包扳手
DOI：
--
发表时间：
2008
期刊：
SIAM journal on computing (Print)
影响因子：
--
作者：
Arnab Bhattacharyya;Elena Grigorescu;Kyomin Jung;Sofya Raskhodnikova;David P. Woodruff
通讯作者：
David P. Woodruff
影响因子：
0.5
作者：
Elkin, Michael;Peleg, David
通讯作者：
Peleg, David
影响因子：
1
作者：
P. Berman;Arnab Bhattacharyya;K. Makarychev;Sofya Raskhodnikova;G. Yaroslavtsev
通讯作者：
G. Yaroslavtsev