11:31
官方一手arXiv: OpenAI@Viktor Fredslund-Hansen, Shay Mozes, Oren Weimann
推荐理由：这篇把平面图距离模式上界从O(k^3)压到O(k^2)，还顺手改进了直径算法，连GPT-5.6-Sol都参与证明了。
距离模式
共 1 条相关 AI 资讯
8月10日
11:31
论文针对无向无权平面图，研究顶点到指定面上所有顶点的距离向量模式。作者将Li和Parter在STOC'19给出的O(k^3)上界改进到O(k^2)，匹配已知下界，并解决了ISAAC'22中的猜想。新界直接改进了Okamura-Seymour度量的压缩、常数时间精确距离预言机的空间，以及分布式直径算法。另外还给出集中式O~(n^{8/5})时间直径算法，优于SODA'18的O~(n^{5/3})。简单证明由OpenAI的GPT 5.6-Sol模型发现。