{"id":"arxiv/2605.07408","url":"https://arxiv.org/abs/2605.07408","tags":["math.NA"],"score":0,"title":"Newton's method for optimal transport problem on graphs","domain":"math.NA","source":"arxiv","authors":["Qujiangxue Chen","Jianbo Cui","Luca Dieci","Haomin Zhou"],"reviews":0,"subject":"math.NA","summary":"In this paper, we study dynamical optimal transport on a connected graph from the perspective of the Benamou-Brenier formulation, where densities are assigned to vertices and velocities to edges. However, directly using Newton's method on the resulting nonlinear systems encounters two potential difficulties: (i) if the graph contains cycles, edge variables are not unique, and (ii) there is no guarantee that the density variables remain positive. To address these challenges, we introduce a finite-difference-type Newton method that eliminates cycle-induced redundancies through a spanning-tree…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-08","reactions":{}}