# On Assignment Problems Related to Gromov-Wasserstein Distances on the Real Line

arXiv: https://arxiv.org/abs/2205.09006 · HTML: https://mlsanity.com/paper/2205.09006/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2022.

## Built on by (most cited first, 8 of 8)

- [A Novel Sliced Fused Gromov-Wasserstein Distance](https://mlsanity.com/paper/2508.02364/) (2025)
- [On Probabilistic Embeddings in Optimal Dimension Reduction](https://mlsanity.com/paper/2408.02433/) (2024)
- [Normalized Radon Cumulative Distribution Transforms for Invariance and Robustness in Optimal Transport Based Image Classification](https://mlsanity.com/paper/2506.08761/) (2025)
- [Sliced Inner Product Gromov-Wasserstein Distances](https://mlsanity.com/paper/2605.08546/) (2026)
- [Relation-Aware Slicing in Cross-Domain Alignment](https://mlsanity.com/paper/2507.13194/) (2025)
- [Generalizations of the Normalized Radon Cumulative Distribution Transform for Limited Data Recognition](https://mlsanity.com/paper/2512.08099/) (2025)
- [Min Generalized Sliced Gromov Wasserstein: A Scalable Path to Gromov Wasserstein](https://mlsanity.com/paper/2605.13753/) (2026)
- [Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithms](https://mlsanity.com/paper/2608.11016/) (2026)

## Abstract (arXiv)

Let x1 < dots < xn and y1 < dots < yn, n ∈ mathbb N, be real numbers. We show by an example that the assignment problem  maxσ ∈ Sn Fσ(x,y) := frac12 sumi,k=1n |xi - xk|α , |yσ(i) - yσ(k)|α, quad α >0,  is in general neither solved by the identical permutation (id) nor the anti-identical permutation (a-id) if n > 2 +2α. Indeed the above maximum can be, depending on the number of points, arbitrary far away from Fid(x,y) and Fa-id(x,y). The motivation to deal with such assignment problems came from their relation to Gromov-Wasserstein divergences which have recently attained a lot of attention.