The NP-hardness of the Gromov-Wasserstein distance

Autor:	Kravtsova, Natalia
Rok vydání:	2024
Předmět:	Statistics - Machine Learning Computer Science - Machine Learning
Druh dokumentu:	Working Paper
Popis:	This note addresses the property frequently mentioned in the literature that the Gromov-Wasserstein (GW) distance is NP-hard. We provide the details on the non-convex nature of the GW optimization problem that imply NP-hardness of the GW distance between finite spaces for any instance of an input data. We further illustrate the non-convexity of the problem with several explicit examples.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2408.06525 Zobrazit plný text záznamu View this record from Arxiv