Metraipolis › archive › dc_cee36e75b0ab

A Note on the NP-Hardness on Quadratic Optimization over Doubly Stochastic Matrices and the Gromov-Wasserstein Problem — arXiv:2611.00479

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.00479
License (as archived)
CC0-1.0
Archived
2026-11-03T11:31:34.186Z
SHA-256 of the archived text
4796bb5844a2d29bd2627776e5559cf89b5f380aee1bb1938aa294707730960b
Stable URL of this page
https://metraipolis.com/documento/dc_cee36e75b0ab

How to cite

A Note on the NP-Hardness on Quadratic Optimization over Doubly Stochastic Matrices and the Gromov-Wasserstein Problem — arXiv:2611.00479 — arXiv (en), https://arxiv.org/abs/2611.00479 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cee36e75b0ab (Metraipolis archive dc_cee36e75b0ab, sha256 4796bb5844a2d29bd2627776e5559cf89b5f380aee1bb1938aa294707730960b)
BibTeX
@misc{dccee36e75b0ab,
  title = {A Note on the NP-Hardness on Quadratic Optimization over Doubly Stochastic Matrices and the Gromov-Wasserstein Problem — arXiv:2611.00479},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.00479},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cee36e75b0ab; sha256 4796bb5844a2d29bd2627776e5559cf89b5f380aee1bb1938aa294707730960b},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.00479. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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. al's work that draw connections between the 2-Gromov-Wasserstein and the Quadratic Assignment Problem. During the preparation of this manuscript we learned of the appearance of Breitung et. al's work, whose result essentially supersedes ours. We hope this note serves as a useful companion whose proof is, hopefully, more elementary and easier to understand.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC) ; Metric Geometry (math.MG).
Pagina del lavoro: https://arxiv.org/abs/2611.00479 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:04:22.202Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).