{"id":"arxiv/2605.05877","url":"https://arxiv.org/abs/2605.05877","tags":["cs.DS","math.PR"],"score":0,"title":"Discrete Optimal Transport: Rapid Convergence of Simulated Annealing Algorithms","domain":"cs.DS","source":"arxiv","authors":["Yuchen He","Tianhui Jiang","Sihan Wang","Chihao Zhang"],"reviews":0,"subject":"cs.DS","summary":"We develop a discrete optimal transport framework for analyzing simulated annealing algorithms on finite state spaces. Building on the discrete Wasserstein metric introduced by Maas (J. Funct. Anal., 2011), we define a generalized discrete Wasserstein-2 distance and the associated notion of \\emph{discrete action} for paths of probability measures on graphs. Using these tools, we establish non-asymptotic convergence guarantees for simulated annealing: the KL divergence between the algorithm's output and the target distribution is controlled by the discrete action of the annealing path. This…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-07","reactions":{}}