在图论中，Okamura-Seymour准度量 $(T,\,\boldsymbol{\delta}_T)$ 如果存在一个边权平面嵌入有向图 $G = (V, E, w)$，使得 $T$ 是 $G$ 外面上的一组终端，并且对于每对 $(t,t') \in T \times T$，有 $\boldsymbol{\delta}_G(t,t') = \boldsymbol{\delta}_T(t,t')$，则称为Okamura-Seymour准度量。最近，Chen和Tan提出了一个多项式时间算法来测试给定的准度量 $(T,\boldsymbol{\delta}_T)$ 是否为Okamura-Seymour准度量。该证明中的关键步骤是存在性的，这足以为高效的测试算法提供支持，但并不意味着存在高效的嵌入算法。
我们的论文通过线性规划实现了他们的存在性步骤，从而填补了这一空白。结果是，我们获得了第一个多项式时间算法，用于找到任何给定Okamura-Seymour准度量 $(T,\boldsymbol{\delta}_T)$ 的平面嵌入。作为应用，我们展示了如何利用Okamura-Seymour准度量的平面嵌入，在分布式CONGEST模型中计算平面有向图的$(1+\epsilon)$-近似单源最短路径（SSSP），所需轮数为 $\tilde{O}(D)$，对于任何固定的 $\epsilon \in (0,1)$，几乎匹配了简单的下界 $\Omega(D)$，并解决了该领域的一个基本问题。该问题的已知最佳算法的轮复杂度为 $\tilde{O}(D^2)$。
博主点评： 本文通过线性规划技术成功实现了Okamura-Seymour准度量的平面嵌入，为分布式计算中的单源最短路径问题提供了高效解决方案。其方法的多项式时间复杂度将推动相关研究的进一步发展，值得关注。