Iterative Message Passing Algorithm for Vertex-Disjoint Shortest Paths
Iterative Message Passing Algorithm for Vertex-Disjoint Shortest Paths
复制标题
DOI：
10.1109/tit.2022.3145232
复制
发表时间：
2022-06
影响因子：
2.5
通讯作者：
Guowei Dai;Longkun Guo;G. Gutin;Xiaoyan Zhang;Zan-Bo Zhang
中科院分区：
文献类型：
--
作者：
Guowei Dai;Longkun Guo;G. Gutin;Xiaoyan Zhang;Zan-Bo Zhang
作为一个算法框架，消息传递是非常强大的，并在不同学科的背景下，包括通信，编码理论，统计学，信号处理，人工智能和组合优化有着广泛的应用。在本文中，我们研究的消息传递算法称为最小和信念传播（BP）的顶点不相交的最短<inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-路径问题（<inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-VDSP）的加权有向图的性能，并推导出迭代的消息传递更新规则。作为本文的主要结果，我们证明了对于n<inline-formula><tex-math notation="LaTeX">阶</tex-math></inline-formula>加权有向<inline-formula><tex-math notation="LaTeX">图G</tex-math></inline-formula>，BP算法在<inline-formula><tex-math notation="LaTeX">O（n^{2}w_{max}）$次</tex-math></inline-formula>迭代内收敛<inline-formula><tex-math notation="LaTeX">到</tex-math></inline-formula>G<inline-formula><tex-math notation="LaTeX">上k</tex-math></inline-formula>-VDSP的唯一最优解，条件是对<inline-formula><tex-math notation="LaTeX">E（G）中的</tex-math></inline-formula>每一条弧<inline-formula><tex-math notation="LaTeX">w_{e}都</tex-math></inline-formula>是非负整数，其中<inline-formula><tex-math notation="LaTeX">w_{max}=\max \{w_{e}：e\in E（G）\}</tex-math></inline-formula>。据我们所知，这是BP算法被证明是正确的NP-难问题的第一个例子。此外，我们建立的扩展<inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-VDSP的情况下，多个源或汇。
As an algorithmic framework, message passing is extremely powerful and has wide applications in the context of different disciplines including communications, coding theory, statistics, signal processing, artificial intelligence and combinatorial optimization. In this paper, we investigate the performance of a message-passing algorithm called min-sum belief propagation (BP) for the vertex-disjoint shortest <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-path problem (<inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-VDSP) on weighted directed graphs, and derive the iterative message-passing update rules. As the main result of this paper, we prove that for a weighted directed graph <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> of order <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>, BP algorithm converges to the unique optimal solution of <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-VDSP on <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula> within <inline-formula> <tex-math notation="LaTeX">$O(n^{2}w_{max})$ </tex-math></inline-formula> iterations, provided that the weight <inline-formula> <tex-math notation="LaTeX">$w_{e}$ </tex-math></inline-formula> is nonnegative integral for each arc <inline-formula> <tex-math notation="LaTeX">$e\in E(G)$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$w_{max}=\max \{w_{e}: e\in E(G)\}$ </tex-math></inline-formula>. To the best of our knowledge, this is the first instance where BP algorithm is proved correct for NP-hard problems. Additionally, we establish the extensions of <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-VDSP to the case of multiple sources or sinks.