{"id":"arxiv/2611.00479","url":"https://arxiv.org/abs/2611.00479","tags":["math.OC","math.MG"],"score":0,"title":"A Note on the NP-Hardness on Quadratic Optimization over Doubly Stochastic Matrices and the Gromov-Wasserstein Problem","domain":"math.OC","source":"arxiv","authors":["Yong Sheng Soh"],"reviews":0,"subject":"math.OC","summary":"The Gromov-Wasserstein problem is an extension of the regular optimal transport problem that is adapted for pairs of distributions residing in incomparable spaces. Broadly speaking, given a pair of metric measure spaces, the Gromov-Wasserstein problem seeks couplings between these spaces that minimize the distortion between the metric evaluations. In this note we record the fact that the Gromov-Wasserstein distance between finite metric spaces is NP-Hard to compute. Our argument relies on a reduction from the Hamiltonian Cycle Problem, and it builds on ideas in Vayer's thesis and Ryner et.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-31","reactions":{}}