Pith. sign in

REVIEW 4 major objections 6 minor 80 references

The paper claims that capacitated quadratic assignment problems can be solved through Gromov-Wasserstein optimal transport, and that a multi-start variant finds near-optimal solutions in seconds where exact solvers stall.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

A largely expository paper connecting assignment problems to optimal transport and Gromov-Wasserstein distances, with a benchmark claiming a multi-start GW heuristic finds near-optimal capacitated QAP solutions; the benchmark evidence is internally inconsistent.

T0 review reviewed 2026-08-05 challenge →

load-bearing objection A wide-ranging survey of OT/GW connections to assignment problems, plus a benchmark for a multi-start GW heuristic on capacitated QAP; the benchmark's headline claim is unsupported because the objective is undefined and no feasible rounding is given. the 4 major comments →

arxiv 2509.04089 v1 pith:QSSH3HEZ submitted 2025-09-04 math.OC cs.LG

Gromov-Wasserstein and optimal transport: from assignment problems to probabilistic numeric

Iman Seyedi , Antonio Candelieri , Enza Messina , Francesco Archetti This is my paper
classification math.OC cs.LG MSC 49Q2290C2790C26
keywords Optimal transportGromov-WassersteinQuadratic assignment problemCapacitated QAPMulti-initializationEntropic regularizationFused Gromov-WassersteinSinkhorn algorithm
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish a single line of descent from classical assignment problems through optimal transport to Gromov-Wasserstein (GW) matching, and to show that this line is practically useful for the NP-hard Capacitated Quadratic Assignment Problem (CQAP). Its central computational claim is that running a standard GW solver from several random feasible couplings, the proposed GW_MultiInit strategy, escapes poor local optima and returns near-optimal assignments on synthetic CQAP instances up to 100x100, where exact solvers become impractical. If that claim holds, practitioners facing facility-location, logistics, or graph-matching tasks with capacity and demand constraints get a fast relaxation that is easy to tune and degrades gracefully as problem size grows. The paper also maps the accuracy and runtime trade-offs of entropic and fused GW variants and gives parameter guidance for the regularization strength and the structure-versus-features fusion weight.

Core claim

On its own terms, the paper's discovery is that the quadratic assignment objective, matching pairwise flow interactions to pairwise location distances under capacity and demand constraints, has the same functional form as the GW discrepancy, so CQAP can be treated as a GW problem with capacities and demands encoded as marginal distributions. Because GW is non-convex and NP-hard, the paper proposes GW_MultiInit: solve GW from the default initialization, then from T random couplings projected onto the marginal polytope, keeping the lowest-loss plan. In experiments, this strategy matched the exact mixed-integer quadratic solution on the smallest instances, averaged a 1.78 percent gap on exact-s

What carries the argument

The central object is the Gromov-Wasserstein discrepancy: the minimum over couplings pi with prescribed marginals of sum |C1(i,j)-C2(k,l)|^q pi_{i,k} pi_{j,l}, comparing the internal pairwise dissimilarity matrices of two spaces. This is what turns assignment problems into transport problems, because the quadratic QAP term is the GW loss when the flow and distance matrices are read as intra-domain dissimilarities. Two accelerations carry the computational story: entropic regularization adds epsilon times the KL divergence to the objective so that Sinkhorn matrix scaling applies, and fused GW mixes a feature-cost matrix with the structural GW loss through a weight alpha. The multi-initializat

Load-bearing premise

The load-bearing premise is that encoding CQAP capacities and demands as GW marginals, and replacing binary assignments with fractional transport plans, preserves the problem's optimum closely enough that near-optimal GW plans are near-optimal CQAP assignments; the paper asserts this bridge without proving it or specifying how to round plans back to feasible binary assignments.

What would settle it

Take a CQAP instance from Table 7 with a known exact optimum, run GW_MultiInit, round the returned fractional plan to a binary assignment that respects capacity and demand constraints, and evaluate the original CQAP objective on that rounded assignment; if the rounded objective exceeds the exact optimum by substantially more than the reported 1.78 percent average gap, the central bridge fails.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • On instances with known exact solutions, GW_MultiInit matches the exact optimum on the 3x3, 4x4, and 6x5 cases, comes within 9.9 percent on 10x10, and averages a 1.78 percent gap overall.
  • For large CQAP instances up to 100x100 where exact methods are impractical, GW_MultiInit reports the lowest objective value among all tested methods on every large instance.
  • EGW with epsilon around 0.8 is the recommended accuracy-speed compromise, with an average gap of 7.08 percent and moderate runtime.
  • FGW with alpha equal to 0.7 substantially outperforms feature-heavy settings, indicating that structural information matters more than feature alignment for CQAP.
  • GW-based methods scale far better than exact mixed-integer quadratic programming and genetic algorithms: on 10x10, exact solution takes 732 seconds while all GW variants finish in under 0.1 seconds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The paper never specifies how the fractional GW transport plan is converted into a binary, capacity-feasible CQAP assignment; if the reported objective is evaluated on the unrounded plan, the near-optimal gaps are not yet demonstrated for feasible integer solutions.
  • CQAP constraints are inequalities, capacity limits and demand satisfaction, while GW enforces exact equality marginals; encoding the slack as exact marginal mass is a modeling choice, so a partial or unbalanced GW formulation would be a more faithful relaxation.
  • The uniform random multi-start idea could be sharpened by using low-discrepancy or Bayesian-search initializations over the coupling polytope, but the paper does not test this.
  • If the GW-CQAP bridge is validated on real logistics data, the resulting plan could serve directly as a probabilistic assignment under demand uncertainty, with rounding deferred to a final allocation step.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper positions the Quadratic Assignment Problem (QAP) and its capacitated variant (CQAP) inside the Gromov-Wasserstein (GW) optimal transport framework, surveys GW extensions (entropic GW, fused GW, unbalanced variants), and proposes GW_MultiInit, a multi-start strategy that runs a standard GW solver from several random couplings and keeps the lowest-GW-loss plan. Computational experiments on synthetic CQAP instances compare GW variants, a genetic algorithm, and an exact Gurobi MIQP solver. The abstract claims that GW_MultiInit consistently achieves near-optimal solutions and scales to large instances where exact methods are impractical.

Significance. If the central empirical claim were properly supported, the paper would offer a useful practical finding: a simple multi-start wrapper around a standard GW solver can produce near-optimal, scalable solutions for CQAP instances, along with guidance on entropic regularization and fusion parameters. The paper also provides a broad survey and makes code available on GitHub. However, the current manuscript does not establish that the GW optimization problem being solved is the CQAP being benchmarked, and the large-instance evaluation is circular because it ranks methods by the very GW loss that each method minimizes. These issues affect the abstract's main claim, so the numerical contribution is not yet convincing, despite the breadth of the survey and the systematic parameter experiments.

major comments (4)
  1. [§2.4.2, §5 introduction, Eq. (21)] The CQAP-to-GW modeling bridge is asserted rather than demonstrated. The CQAP constraints (14)-(15) are inequalities (capacity ≤, demand ≥) and the variables are binary (16), whereas the GW coupling set in Eq. (21) enforces equality marginals and allows fractional plans. The paper does not give a construction mapping capacities u_i and demands d_j to histograms h and g, does not prove that GW marginal equalities correspond to CQAP feasibility, and gives no rounding or projection from a fractional coupling to a binary assignment. Consequently, the 'Objective' values in Tables 6, 7, and 12 may be GW discrepancies over fractional plans rather than CQAP objectives over feasible binary assignments. This is load-bearing for the abstract's near-optimality claim.
  2. [Tables 6-9 and 12-13] The comparison protocol is undefined. The exact solver minimizes the binary MIQP objective (13), while GW, EGW, and FGW minimize different losses: Eq. (22), Eq. (23), and Eq. (26). The text never defines which objective is reported for the approximate methods, nor whether these are evaluated on the same rounded binary assignment or directly on the fractional coupling. Table 9's gap formula assumes a common objective function. Without a shared evaluation criterion, the reported gaps and 'best method' rankings are not meaningful. The authors should specify a rounding method (e.g., Hungarian rounding of the transport plan) and then evaluate all methods on the same CQAP objective.
  3. [Tables 12-13, §5 large instances] The large-instance evaluation is circular. For instances with no exact solution, the 'best' method is identified by the lowest GW objective value. But every GW variant minimizes that same or a related loss, and GW_MultiInit by construction returns the lowest GW loss among its starts. This does not provide evidence that GW_MultiInit finds better CQAP solutions. The paper should compare against external benchmarks or bounds (e.g., known QAPLIB/CQAP instances, primal-dual gaps, or a rounded CQAP objective) rather than only the objective being minimized.
  4. [Tables 5, 6, and 12] There are internal inconsistencies in the experimental data. Table 5 lists the 15×12 instance as Medium with total mass 43, while Table 12 lists the same 15×12 instance with mass 49 and reports GW_MultiInit objective 8349.234; Table 6 reports 15×12 GW_MultiInit objective 11089.4670. Similarly, Table 6 names GW_Default as best for 20×20 with objective 8405.1519, while Table 12 lists GW_MultiInit at 8405.15. These discrepancies need to be resolved or explained, as they undermine confidence in the reported comparisons.
minor comments (6)
  1. [§6 Conclusion] The first two paragraphs of the conclusion are nearly verbatim duplicates; one copy should be removed.
  2. [§3.2] There is a garbled sentence: 'The GW distance is designed to compare structured mm spaces sounds like a limitation' and the following definition of mm-space has formatting errors. These should be rewritten.
  3. [Throughout] Equation numbers are reused: Eq. (13) appears for both the QAP objective and CQAP objective, and Eq. (17) is used for both the GW quadratic term and the p-Wasserstein distance. Please renumber to make references unambiguous.
  4. [§5, Table 13] The paragraph before Table 13 says 'Table 12 compares the computational efficiency...' but the efficiency data are in Table 13; the cross-reference should be corrected.
  5. [Tables 10-11] For the 3×3 instance, several ε and α settings show '-' without explanation; please clarify whether those runs were not performed or failed.
  6. [Figure 2] The pseudocode uses δ = 1e-12 for the marginal convergence check; this may never terminate in floating point. A tolerance relative to the problem size would be more robust.

Circularity Check

1 steps flagged

Large-instance 'GW_MultiInit best' restates its own selection criterion; small-instance exact comparisons are non-circular.

specific steps
  1. self definitional [Section 4.3 (Figure 2 pseudo-code) and Section 5, Table 12]
    "the solution with the lowest objective value ℒ_GW(P) = Σ (C1_ij − C2_kℓ)^2 P_ik P_jℓ across all trials is returned as the final result ... Among all methods evaluated, GW MultiInit consistently achieves the best (lowest) objective values across all problem sizes."

    GW_MultiInit's output is defined as the restart with minimal ℒ_GW. Table 12 reports an 'Objective' that is never defined as the CQAP objective of Eq. (13); the only objective defined for the GW_MultiInit procedure is ℒ_GW. Therefore, if Table 12's objective is ℒ_GW, the statement 'GW MultiInit achieves the best (lowest) objective' is true by construction — it is exactly the argmin selection rule in Figure 2. The large-instance 'near-optimal CQAP' conclusion thus restates the algorithm's selection criterion rather than testing it against the constrained binary CQAP. The small-instance Gurobi MIQP comparisons are non-circular external checks; the large-instance evaluation is not.

full rationale

The paper's small-instance evaluation is anchored to an external solver (Gurobi MIQP), which provides genuine non-circular evidence that GW_MultiInit can match or approach CQAP optima up to 10x10. The circularity is concentrated in the large-instance claim. Tables 6, 7 and 12 report 'Objective' values without ever stating whether this is the CQAP objective of Eq. (13) or the GW discrepancy of Eq. (22), while the GW_MultiInit algorithm explicitly selects the plan minimizing ℒ_GW. If the tabulated objective is ℒ_GW, then MultiInit's 'best' ranking is the selection rule restated; if it is a CQAP objective, the paper would need to define how fractional couplings are rounded/evaluated, which it does not. Additionally, the modeling bridge from CQAP to GW (Section 2.4.2 to Section 5) is asserted rather than derived: Eq. (14)-(15) are inequality constraints with binary variables, whereas GW's admissible set Eq. (21) imposes equality marginals and permits fractional plans. No construction maps capacities/demands to h,g, and no proof shows equality constraints correspond to the CQAP's ≤ and ≥ constraints. This is a correctness gap rather than circularity, since GW is not defined in terms of CQAP. The average gap of 1.78% in Table 9 also leans on the 12x14 row, where GW_MultiInit's 5405.29 is below the interrupted 'exact' 5951.45 and is entered as 0.00, an artifact that inflates the reported average; again this is a data-integrity concern, not a circular-definition concern. Self-citations ([19], [46], [61], [78], etc.) appear only as background and are not load-bearing. No uniqueness theorem or ansatz is imported via self-citation. Overall: one central large-scale prediction reduces by construction, while small-scale results remain independently grounded, giving a partial circularity score of 6.

Axiom & Free-Parameter Ledger

3 free parameters · 5 axioms · 0 invented entities

The empirical claims rest on three tuned hyperparameters (epsilon, alpha, and the unreported restart count T), on the unproven modeling bridge that GW equality-constrained marginals faithfully proxy the CQAP's inequality capacity and demand constraints, and on the representativeness of synthetic instances drawn uniformly in [0,10]^2. No new entities such as particles, forces, or dimensions are introduced, so invented_entities is empty.

free parameters (3)
  • Entropic regularization epsilon (EGW) = 0.8 (recommended after scan)
    Scanned over 0.3 to 1.0 on the same six small instances used for the headline results (Table 10); the best-performing value is promoted to a default recommendation without hold-out validation.
  • Fusion weight alpha (FGW) = 0.7 (recommended after scan)
    Scanned over 0.0 to 0.7 on the same instances (Table 11); the recommended default is selected on the test instances themselves.
  • Number of random starts T (GW-MultiInit) = not reported
    The pseudo-code in Section 4.3 takes T as input, but the experimental section never states the value used. The headline results are therefore not reproducible from the text alone.
axioms (5)
  • standard math The LAP emerges as the uniform-mass, permutation-restricted special case of Monge and Kantorovich optimal transport.
    Stated in Sections 2.2 and 2.3; classical content (Monge 1781, Kantorovich 1942, Munkres 1957), not novel to this paper.
  • domain assumption The QAP quadratic term is equivalent in form to the GW cost, so CQAP instances can be solved by minimizing a GW discrepancy with marginals set to capacities and demands.
    Sections 2.4.1, 2.4.2 and the Section 5 introduction assert the modeling equivalence without proof. In particular, CQAP inequality capacity and demand constraints are replaced by GW equality marginals, and no mapping from fractional GW plans back to binary feasible assignments is given.
  • standard math The GW distance between finite spaces is NP-hard and its objective is non-convex, so stationary-point and multi-start analyses are appropriate.
    Section 3.2, citing Kravtsova 2025 and Memoli 2011; accepted background.
  • standard math Sinkhorn iteration projects any positive matrix onto the coupling polytope, and the GW solver converges to a stationary point of the GW functional.
    Used in Section 4.3 and the experiments via the POT library; accepted algorithmic background.
  • domain assumption Random uniform 2D positions in [0,10]^2 with random integer capacities and demands constitute representative CQAP instances.
    Section 5 instance generation; no real-world CQAP instances are used, so external validity rests on this assumption.

reviewed 2026-08-05 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Gromov-Wasserstein and optimal transport: from assignment problems to probabilistic numeric." pith.science (2026). https://pith.science/paper/QSSH3HEZ

@misc{pith2026250904089,
  author       = {Pith},
  title        = {Pith review of: Gromov-Wasserstein and optimal transport: from assignment problems to probabilistic numeric},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QSSH3HEZ}},
  note         = {Machine review of arXiv:2509.04089}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

The assignment problem, a cornerstone of operations research, seeks an optimal one-to-one mapping between agents and tasks to minimize total cost. This work traces its evolution from classical formulations and algorithms to modern optimal transport (OT) theory, positioning the Quadratic Assignment Problem (QAP) and related structural matching tasks within this framework. We connect the linear assignment problem to Monge's transport problem, Kantorovich's relaxation, and Wasserstein distances, then extend to cases where source and target lie in different metric-measure spaces requiring Gromov-Wasserstein (GW) distances. GW formulations, including the fused GW variant that integrates structural and feature information, naturally address QAP-like problems by optimizing alignment based on both intra-domain distances and cross-domain attributes. Applications include graph matching, keypoint correspondence, and feature-based assignments. We present exact solvers, Genetic Algorithms (GA), and multiple GW variants, including a proposed multi-initialization strategy (GW-MultiInit) that mitigates the risk of getting stuck in local optima alongside entropic Sinkhorn-based approximations and fused GW. Computational experiments on capacitated QAP instances show that GW-MultiInit consistently achieves near-optimal solutions and scales efficiently to large problems where exact methods become impractical, while parameterized EGW and FGW variants provide flexible trade-offs between accuracy and runtime. Our findings provide theoretical foundations, computational insights, and practical guidelines for applying OT and GW methods to QAP and other real-world matching problems, such as those in machine learning and logistics.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

80 extracted references · 67 canonical work pages · 2 internal anchors

  1. [1]

    Burkard, M

    R. Burkard, M. Dell’Amico, and S. Martello, ‘Assignment problems: revised reprint’, in Assignment Problems, Society for Industrial and Applied Mathematics, 2012, pp. 327–393. doi: 10.1137/1.9781611972238.bm

    work page doi:10.1137/1.9781611972238.bm 2012

  2. [2]

    D. W. Pentico, ‘Assignment problems: A golden anniversary survey’, Eur. J. Oper. Res., vol. 176, no. 2, pp. 774–793, 2007

    work page 2007

  3. [3]

    Seyedi, S

    I. Seyedi, S. Mirzazadeh, A. Maleki-Daronkolaei, M. Mukhtar, and S. Sahran, ‘An inventory model with reworking and setup time to consider effect of inflation and time value of money’, J. Eng. Sci. Technol., vol. 11, no. 3, pp. 416–430, 2016

    work page 2016

  4. [4]

    Munkres, ‘Algorithms for the Assignment and Transportation Problems’, J

    J. Munkres, ‘Algorithms for the Assignment and Transportation Problems’, J. Soc. Ind. Appl. Math., vol. 5, no. 1, pp. 32–38, Mar. 1957, doi: 10.1137/0105003

    doi:10.1137/0105003 1957

  5. [5]

    H. W. Kuhn, ‘The Hungarian method for the assignment problem’, Nav. Res. Logist. Q., vol. 2, no. 1–2, pp. 83–97, Mar. 1955, doi: 10.1002/nav.3800020109

    doi:10.1002/nav.3800020109 1955

  6. [6]

    C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity. Courier Corporation, 1998. Accessed: Jul. 17, 2025. [Online]. Available: https://books.google.com/books?hl=en&lr=&id=cDY- joeCGoIC&oi=fnd&pg=PP1&dq=Papadimitriou,+C.+H.,+%26+Steiglitz,+K.+(1998).+Combinatori al+optimization:+Algorithms+and+complexity.+Courier+Corp...

    work page 1998

  7. [8]

    Laporte, ‘Fifty Years of Vehicle Routing’, Transp

    G. Laporte, ‘Fifty Years of Vehicle Routing’, Transp. Sci., vol. 43, no. 4, pp. 408–416, Nov. 2009, doi: 10.1287/trsc.1090.0301

    work page arXiv 2009

  8. [9]

    T. C. Koopmans and M. Beckmann, ‘Assignment problems and the location of economic activities’, Econom. J. Econom. Soc., pp. 53–76, 1957

    work page 1957

  9. [10]

    Sahni and T

    S. Sahni and T. Gonzalez, ‘P-Complete Approximation Problems’, J. ACM, vol. 23, no. 3, pp. 555– 565, Jul. 1976, doi: 10.1145/321958.321975

    work page arXiv 1976

  10. [11]

    P. M. Pardalos and S. A. Vavasis, ‘Quadratic programming with one negative eigenvalue is NP- hard’, J. Glob. Optim., vol. 1, no. 1, pp. 15–22, 1991

    work page 1991

  11. [12]

    Kravtsova, ‘The NP-hardness of the Gromov-Wasserstein distance’, Mar

    N. Kravtsova, ‘The NP-hardness of the Gromov-Wasserstein distance’, Mar. 07, 2025, arXiv: arXiv:2408.06525. doi: 10.48550/arXiv.2408.06525. 34

    work page doi:10.48550/arxiv.2408.06525 2025

  12. [13]

    Villani, Topics in optimal transportation, vol

    C. Villani, Topics in optimal transportation, vol. 58. American Mathematical Soc., 2021. Accessed: Jul. 10, 2025. [Online]. Available: https://books.google.com/books?hl=en&lr=&id=NElDEAAAQBAJ&oi=fnd&pg=PP1&dq=%22top ics+in+Optimal+Transportation%22+%2B%22Villani%22&ots=G9gdzYB0Wj&sig=O626wJETNC eUYWG-zIvSx_8LbYE

    work page 2021

  13. [14]

    Monge, Mémoire sur le calcul intégral des équations aux différences partielles

    G. Monge, Mémoire sur le calcul intégral des équations aux différences partielles. Imprimerie royale, 1784

    work page

  14. [15]

    Kantorovich, ‘On the transfer of masses (in Russian)’, in Doklady Akademii Nauk, 1942, p

    L. Kantorovich, ‘On the transfer of masses (in Russian)’, in Doklady Akademii Nauk, 1942, p. 227. Accessed: Jul. 17, 2025. [Online]. Available: https://cir.nii.ac.jp/crid/1370565168575910170

    work page arXiv 1942

  15. [16]

    S. T. Rachev and L. Rüschendorf, ‘Duality Theory for Mass Transfer Problems’, in Probability and its Applications, New York: Springer-Verlag, pp. 161–273. doi: 10.1007/0-387-22755-5_4

    work page doi:10.1007/0-387-22755-5_4

  16. [17]

    E. F. Montesuma, F. M. N. Mboula, and A. Souloumiac, ‘Recent advances in optimal transport for machine learning’, IEEE Trans. Pattern Anal. Mach. Intell., 2024, Accessed: Jun. 17, 2025. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/10740308/

    work page arXiv 2024

  17. [18]

    Khamis, R

    A. Khamis, R. Tsuchida, M. Tarek, V . Rolland, and L. Petersson, ‘Scalable optimal transport methods in machine learning: A contemporary survey’, IEEE Trans. Pattern Anal. Mach. Intell., 2024, Accessed: Jul. 17, 2025. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/10476763/

    work page arXiv 2024

  18. [19]

    Candelieri, A

    A. Candelieri, A. Ponti, and F. Archetti, ‘Wasserstein enabled Bayesian optimization of composite functions’, J. Ambient Intell. Humaniz. Comput., vol. 14, no. 8, pp. 11263–11271, Aug. 2023, doi: 10.1007/s12652-023-04640-7

    work page doi:10.1007/s12652-023-04640-7 2023

  19. [20]

    Kaňková, ‘Stochastic optimization problems with nonlinear dependence on a probability measure via the Wasserstein metric’, J

    V . Kaňková, ‘Stochastic optimization problems with nonlinear dependence on a probability measure via the Wasserstein metric’, J. Glob. Optim., vol. 90, no. 3, pp. 593–617, Nov. 2024, doi: 10.1007/s10898-024-01380-6

    work page doi:10.1007/s10898-024-01380-6 2024

  20. [21]

    Schiebinger et al., ‘Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming’, Cell, vol

    G. Schiebinger et al., ‘Optimal-transport analysis of single-cell gene expression identifies developmental trajectories in reprogramming’, Cell, vol. 176, no. 4, pp. 928–943, 2019

    work page 2019

  21. [22]

    Rubner, ‘The earth mover’s distance as a metric for image retrieval’, Int

    Y . Rubner, ‘The earth mover’s distance as a metric for image retrieval’, Int. J. Comput. Vis., vol. 40, no. 2, pp. 99–121, 2000, doi: 10.1023/a:1026543900054

    doi:10.1023/a:1026543900054 2000

  22. [23]

    Blanchet, J

    J. Blanchet, J. Li, S. Lin, and X. Zhang, ‘Distributionally Robust Optimization and Robust Statistics’, Jan. 26, 2024, arXiv: arXiv:2401.14655. doi: 10.48550/arXiv.2401.14655

    Pith/arXiv arXiv doi:10.48550/arxiv.2401.14655 2024

  23. [24]

    Bertsekas, Network optimization: continuous and discrete models, vol

    D. Bertsekas, Network optimization: continuous and discrete models, vol. 8. Athena Scientific,

    work page

  24. [25]

    Cuturi, ‘Sinkhorn distances: Lightspeed computation of optimal transport’, Adv

    M. Cuturi, ‘Sinkhorn distances: Lightspeed computation of optimal transport’, Adv. Neural Inf. Process. Syst., vol. 26, 2013, Accessed: Jun. 09, 2025. [Online]. Available: https://proceedings.neurips.cc/paper/2013/hash/af21d0c97db2e27e13572cbf59eb343d-Abstract.html

    work page 2013

  25. [26]

    17, 2025

    Accessed: Jul. 17, 2025. [Online]. Available: https://books.google.com/books?hl=en&lr=&id=qUUxEAAAQBAJ&oi=fnd&pg=PR1&dq=Bertsek as,+D.+P.+(1998).+Network+optimization:+Continuous+and+discrete+models.+Athena+Scientific. &ots=58tND5zlVU&sig=O14j0G8Nixxa2aR0lSZ8ObJf5Sw

    work page 2025

  26. [27]

    Flamary et al., ‘Pot: Python optimal transport’, J

    R. Flamary et al., ‘Pot: Python optimal transport’, J. Mach. Learn. Res., vol. 22, no. 78, pp. 1–8, 2021

    work page 2021

  27. [28]

    Altschuler, J

    J. Altschuler, J. Niles-Weed, and P. Rigollet, ‘Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration’, Adv. Neural Inf. Process. Syst., vol. 30, 2017, Accessed: Jun. 09,

    work page 2017

  28. [29]

    Peyré and M

    G. Peyré and M. Cuturi, ‘Computational optimal transport: With applications to data science’, Found. Trends® Mach. Learn., vol. 11, no. 5–6, pp. 355–607, 2019. 35

    work page 2019

  29. [30]

    Korotin, D

    A. Korotin, D. Selikhanovych, and E. Burnaev, ‘Neural Optimal Transport’, Mar. 01, 2023, arXiv: arXiv:2201.12220. doi: 10.48550/arXiv.2201.12220

    Pith/arXiv arXiv doi:10.48550/arxiv.2201.12220 2023

  30. [31]

    Genevay, M

    A. Genevay, M. Cuturi, G. Peyré, and F. Bach, ‘Stochastic optimization for large-scale optimal transport’, Adv. Neural Inf. Process. Syst., vol. 29, 2016, Accessed: Jul. 17, 2025. [Online]. Available: https://proceedings.neurips.cc/paper/2016/hash/2a27b8144ac02f67687f76782a3b5d8f- Abstract.html

    work page 2016

  31. [33]

    Vayer, L

    T. Vayer, L. Chapel, R. Flamary, R. Tavenard, and N. Courty, ‘Optimal Transport for structured data with application on graphs’, May 13, 2019, arXiv: arXiv:1805.09114. doi: 10.48550/arXiv.1805.09114

    Pith/arXiv arXiv doi:10.48550/arxiv.1805.09114 2019

  32. [34]

    Bunne, D

    C. Bunne, D. Alvarez-Melis, A. Krause, and S. Jegelka, ‘Learning generative models across incomparable spaces’, in International conference on machine learning, PMLR, 2019, pp. 851–861. Accessed: Jul. 17, 2025. [Online]. Available: http://proceedings.mlr.press/v97/bunne19a?ref=https://githubhelp.com

    work page 2019

  33. [35]

    Zhang, Z

    W. Zhang, Z. Wang, J. Fan, H. Wu, and Y . Zhang, ‘Fast Gradient Computation for Gromov- Wasserstein Distance’, Apr. 13, 2024, arXiv: arXiv:2404.08970. doi: 10.48550/arXiv.2404.08970

    Pith/arXiv arXiv doi:10.48550/arxiv.2404.08970 2024

  34. [36]

    Rioux, Z

    G. Rioux, Z. Goldfeld, and K. Kato, ‘Entropic gromov-wasserstein distances: Stability and algorithms’, J. Mach. Learn. Res., vol. 25, no. 363, pp. 1–52, 2024

    work page 2024

  35. [37]

    X. Gong, S. Nietert, and Z. Goldfeld, ‘Robust Alignment via Partial Gromov-Wasserstein Distances’, Jun. 26, 2025, arXiv: arXiv:2506.21507. doi: 10.48550/arXiv.2506.21507

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2506.21507 2025

  36. [38]

    Beier, R

    F. Beier, R. Beinert, and G. Steidl, ‘On a linear Gromov–Wasserstein distance’, IEEE Trans. Image Process., vol. 31, pp. 7292–7305, 2022

    work page 2022

  37. [39]

    H. Xu, D. Luo, and L. Carin, ‘Scalable Gromov-Wasserstein learning for graph partitioning and matching’, Adv. Neural Inf. Process. Syst., vol. 32, 2019, Accessed: Jul. 30, 2025. [Online]. Available: https://proceedings.neurips.cc/paper/2019/hash/6e62a992c676f611616097dbea8ea030- Abstract.html

    work page 2019

  38. [40]

    Peyré, ‘Entropic Approximation of Wasserstein Gradient Flows’, SIAM J

    G. Peyré, ‘Entropic Approximation of Wasserstein Gradient Flows’, SIAM J. Imaging Sci., vol. 8, no. 4, pp. 2323–2351, Jan. 2015, doi: 10.1137/15M1010087

    work page doi:10.1137/15m1010087 2015

  39. [41]

    Séjourné, G

    T. Séjourné, G. Peyré, and F.-X. Vialard, ‘Unbalanced optimal transport, from theory to numerics’, Handb. Numer. Anal., vol. 24, pp. 407–471, 2023

    work page 2023

  40. [42]

    Titouan, R

    V . Titouan, R. Flamary, N. Courty, R. Tavenard, and L. Chapel, ‘Sliced gromov-wasserstein’, Adv. Neural Inf. Process. Syst., vol. 32, 2019, Accessed: Jul. 30, 2025. [Online]. Available: https://proceedings.neurips.cc/paper/2019/hash/a9cc6694dc40736d7a2ec018ea566113- Abstract.html

    work page 2019

  41. [43]

    Séjourné, F.-X

    T. Séjourné, F.-X. Vialard, and G. Peyré, ‘The unbalanced gromov wasserstein distance: Conic formulation and relaxation’, Adv. Neural Inf. Process. Syst., vol. 34, pp. 8766–8779, 2021

    work page 2021

  42. [44]

    Mémoli and T

    F. Mémoli and T. Needham, ‘Comparison results for Gromov–Wasserstein and Gromov–Monge distances’, ESAIM Control Optim. Calc. Var., vol. 30, p. 78, 2024, doi: 10.1051/cocv/2024063

    work page arXiv 2024

  43. [45]

    Titouan, I

    V . Titouan, I. Redko, R. Flamary, and N. Courty, ‘Co-optimal transport’, Adv. Neural Inf. Process. Syst., vol. 33, pp. 17559–17570, 2020

    work page 2020

  44. [46]

    Peyré, M

    G. Peyré, M. Cuturi, and J. Solomon, ‘Gromov-wasserstein averaging of kernel and distance matrices’, in International conference on machine learning, PMLR, 2016, pp. 2664–2672. Accessed: Jul. 09, 2025. [Online]. Available: http://proceedings.mlr.press/v48/peyre16.html

    work page 2016

  45. [47]

    R. D. Martín, I. V . Medri, and J. M. Murphy, ‘Gromov-Wasserstein Barycenters: The Analysis Problem’, Jul. 14, 2025, arXiv: arXiv:2507.09865. doi: 10.48550/arXiv.2507.09865

    work page doi:10.48550/arxiv.2507.09865 2025

  46. [48]

    Petric Maretic, M

    H. Petric Maretic, M. El Gheche, G. Chierchia, and P. Frossard, ‘Got: an optimal transport framework for graph comparison’, Adv. Neural Inf. Process. Syst., vol. 32, 2019, Accessed: Aug. 15,

    work page 2019

  47. [49]

    Candelieri, A

    A. Candelieri, A. Ponti, and F. Archetti, ‘Gaussian Process regression over discrete probability measures: on the non-stationarity relation between Euclidean and Wasserstein Squared Exponential Kernels’, J. Glob. Optim., vol. 92, no. 2, pp. 253–278, Jun. 2025, doi: 10.1007/s10898-025-01463-y

    work page doi:10.1007/s10898-025-01463-y 2025

  48. [50]

    Candelieri, A

    A. Candelieri, A. Ponti, and F. Archetti, ‘Bayesian optimization over the probability simplex’, Ann. Math. Artif. Intell., vol. 93, no. 1, pp. 77–91, Feb. 2025, doi: 10.1007/s10472-023-09883-w

    work page doi:10.1007/s10472-023-09883-w 2025

  49. [51]

    Jiao and J.-P

    Y . Jiao and J.-P. Vert, ‘The Kendall and Mallows kernels for permutations’, in International Conference on Machine Learning, PMLR, 2015, pp. 1935–1944. Accessed: Aug. 15, 2025. [Online]. Available: http://proceedings.mlr.press/v37/jiao15.html

    work page 2015

  50. [52]

    Available: https://proceedings.neurips.cc/paper/2019/hash/fdd5b16fc8134339089ef25b3cf0e588-Abstract.html

    [Online]. Available: https://proceedings.neurips.cc/paper/2019/hash/fdd5b16fc8134339089ef25b3cf0e588-Abstract.html

    work page 2019

  51. [53]

    Deshwal, S

    A. Deshwal, S. Belakaria, J. R. Doppa, and D. H. Kim, ‘Bayesian optimization over permutation spaces’, in Proceedings of the AAAI conference on artificial intelligence, 2022, pp. 6515–6523. 36 Accessed: Aug. 15, 2025. [Online]. Available: https://ojs.aaai.org/index.php/AAAI/article/view/20604

    work page 2022

  52. [54]

    Chang, Y

    W. Chang, Y . Shi, H. Tuan, and J. Wang, ‘Unified optimal transport framework for universal domain adaptation’, Adv. Neural Inf. Process. Syst., vol. 35, pp. 29512–29524, 2022

    work page 2022

  53. [55]

    M. R. Manglik, Introduction to Operations Research. EduGorilla Publication, 2024. Accessed: Jul. 10, 2025. [Online]. Available: https://books.google.com/books?hl=en&lr=&id=- to6EQAAQBAJ&oi=fnd&pg=PP1&dq=%22Introduction+to+Operations+Research%22+&ots=gzG dWQ6_yB&sig=INkcufwnhVQNTCRvGRi5ohhDdLo

    work page 2024

  54. [56]

    Xie and L

    Z. Xie and L. Chen, ‘Merge Kernel for Bayesian Optimization on Permutation Space’, Jul. 18, 2025, arXiv: arXiv:2507.13263. doi: 10.48550/arXiv.2507.13263

    work page doi:10.48550/arxiv.2507.13263 2025

  55. [57]

    De Plaen, P.-F

    H. De Plaen, P.-F. De Plaen, J. A. Suykens, M. Proesmans, T. Tuytelaars, and L. Van Gool, ‘Unbalanced optimal transport: A unified framework for object detection’, in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2023, pp. 3198–3207. Accessed: Jul. 17, 2025. [Online]. Available: http://openaccess.thecvf.com/content/CVP...

    work page 2023

  56. [58]

    Cela, The quadratic assignment problem: theory and algorithms, vol

    E. Cela, The quadratic assignment problem: theory and algorithms, vol. 1. Springer Science & Business Media, 2013. Accessed: Aug. 17, 2025. [Online]. Available: https://books.google.com/books?hl=en&lr=&id=20QGCAAAQBAJ&oi=fnd&pg=PR9&dq=E.+Cel a,+The+Quadratic+Assignment+Problem:+Theory+and+Algorithms,+Kluwer+Academic+Publisher s,+1998.&ots=NmahUD6m1b&sig=Y...

    work page 2013

  57. [59]

    Cuturi and A

    M. Cuturi and A. Doucet, ‘Fast computation of Wasserstein barycenters’, in International conference on machine learning, PMLR, 2014, pp. 685–693. Accessed: Jun. 09, 2025. [Online]. Available: https://proceedings.mlr.press/v32/cuturi14.html

    work page 2014

  58. [61]

    W. A. Chaovalitwongse, I. P. Androulakis, and P. M. Pardalos, ‘Quadratic Integer Programming: Complexity and Equivalent Forms’, in Encyclopedia of Optimization, P. M. Pardalos and O. A. Prokopyev, Eds., Cham: Springer International Publishing, 2024, pp. 1–8. doi: 10.1007/978-3-030- 54621-2_536-1

    doi:10.1007/978-3-030- 2024

  59. [62]

    Mallasto and A

    A. Mallasto and A. Feragen, ‘Learning from uncertain curves: The 2-Wasserstein metric for Gaussian processes’, Adv. Neural Inf. Process. Syst., vol. 30, 2017, Accessed: Jun. 09, 2025. [Online]. Available: https://proceedings.neurips.cc/paper/2017/hash/7a006957be65e608e863301eb98e1808- Abstract.html

    work page 2017

  60. [63]

    Kullback, ‘Kullback-leibler divergence’

    S. Kullback, ‘Kullback-leibler divergence’. Tech. Rep, 1951

    work page 1951

  61. [64]

    Candelieri, A

    A. Candelieri, A. Ponti, I. Giordani, and F. Archetti, ‘On the use of Wasserstein distance in the distributional analysis of human decision making under uncertainty’, Ann. Math. Artif. Intell., vol. 91, no. 2–3, pp. 217–238, Jun. 2023, doi: 10.1007/s10472-022-09807-0

    work page doi:10.1007/s10472-022-09807-0 2023

  62. [65]

    Seyedi, A

    I. Seyedi, A. Candelieri, and F. Archetti, ‘Distributionally Robust Bayesian Optimization via Sinkhorn-based Wasserstein Barycenter’, Mach. Learn. Knowl. Extr., vol. 7, no. 3, Aug. 2025, doi: https://doi.org/10.3390/make7030090

    work page doi:10.3390/make7030090 2025

  63. [66]

    Wasserstein Barycenter Gaussian Process based Bayesian Optimization

    A. Candelieri, A. Ponti, and F. Archetti, ‘Wasserstein Barycenter Gaussian Process based Bayesian Optimization’, May 18, 2025, arXiv: arXiv:2505.12471. doi: 10.48550/arXiv.2505.12471

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.2505.12471 2025

  64. [67]

    Kerdoncuff, R

    T. Kerdoncuff, R. Emonet, and M. Sebban, ‘Sampled Gromov Wasserstein’, Mach. Learn., vol. 110, no. 8, pp. 2151–2186, Aug. 2021, doi: 10.1007/s10994-021-06035-1

    work page doi:10.1007/s10994-021-06035-1 2021

  65. [68]

    Ponti, I

    A. Ponti, I. Giordani, A. Candelieri, and F. Archetti, ‘Wasserstein-Enabled Leaks Localization in Water Distribution Networks’, Water, vol. 16, no. 3, p. 412, 2024. 37

    work page 2024

  66. [69]

    Dvurechensky, A

    P. Dvurechensky, A. Gasnikov, S. Omelchenko, and A. Tiurin, ‘A Stable Alternative to Sinkhorn’s Algorithm for Regularized Optimal Transport’, in Mathematical Optimization Theory and Operations Research, vol. 12095, A. Kononov, M. Khachay, V . A. Kalyagin, and P. Pardalos, Eds., in Lecture Notes in Computer Science, vol. 12095. , Cham: Springer Internation...

    work page doi:10.1007/978-3-030-49988-4_28 2020

  67. [70]

    Mémoli, ‘Gromov–Wasserstein Distances and the Metric Approach to Object Matching’, Found

    F. Mémoli, ‘Gromov–Wasserstein Distances and the Metric Approach to Object Matching’, Found. Comput. Math., vol. 11, no. 4, pp. 417–487, Aug. 2011, doi: 10.1007/s10208-011-9093-5

    doi:10.1007/s10208-011-9093-5 2011

  68. [71]

    M. Li, J. Yu, H. Xu, and C. Meng, ‘Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification’, J. Comput. Graph. Stat., vol. 32, no. 4, pp. 1512–1523, Oct. 2023, doi: 10.1080/10618600.2023.2165500

    arXiv 2023

  69. [72]

    R. E. Burkard, E. Çela, P . M. Pardalos, and L. S. Pitsoulis, ‘The Quadratic Assignment Problem’, in Handbook of Combinatorial Optimization, D.-Z. Du and P. M. Pardalos, Eds., Boston, MA: Springer US, 1998, pp. 1713–1809. doi: 10.1007/978-1-4613-0303-9_27

    work page doi:10.1007/978-1-4613-0303-9_27 1998

  70. [73]

    Mémoli and T

    F. Mémoli and T. Needham, ‘Distance distributions and inverse problems for metric measure spaces’, Stud. Appl. Math., vol. 149, no. 4, pp. 943–1001, Nov. 2022, doi: 10.1111/sapm.12526

    doi:10.1111/sapm.12526 2022

  71. [74]

    T. Le, N. Ho, and M. Yamada, ‘Flow-based alignment approaches for probability measures in different spaces’, in International conference on artificial intelligence and statistics, PMLR, 2021, pp. 3934–3942. Accessed: Aug. 21, 2025. [Online]. Available: https://proceedings.mlr.press/v130/le21b.html

    work page 2021

  72. [75]

    Z. H. Ahmed, ‘A hybrid algorithm combining lexisearch and genetic algorithms for the quadratic assignment problem’, Cogent Eng., vol. 5, no. 1, p. 1423743, Jan. 2018, doi: 10.1080/23311916.2018.1423743

    arXiv 2018

  73. [76]

    Scetbon, G

    M. Scetbon, G. Peyré, and M. Cuturi, ‘Linear-time gromov wasserstein distances using low rank couplings and costs’, in International Conference on Machine Learning, PMLR, 2022, pp. 19347– 19365. Accessed: Aug. 21, 2025. [Online]. Available: https://proceedings.mlr.press/v162/scetbon22b

    work page 2022

  74. [77]

    R. Sato, M. Cuturi, M. Yamada, and H. Kashima, ‘Fast and Robust Comparison of Probability Measures in Heterogeneous Spaces’, Feb. 10, 2021, arXiv: arXiv:2002.01615. doi: 10.48550/arXiv.2002.01615

    Pith/arXiv arXiv doi:10.48550/arxiv.2002.01615 2021

  75. [78]

    Seyedi, A

    I. Seyedi, A. Candelieri, E. Messina, and F. Archetti, ‘Wasserstein Distributionally Robust Optimization for Chance Constrained Facility Location Under Uncertain Demand’, Mathematics, vol. 13, no. 13, Jun. 2025, doi: 10.3390/math13132144

    work page doi:10.3390/math13132144 2025

  76. [79]

    G. A. E.-N. A. Said, A. M. Mahmoud, and E.-S. M. El-Horbaty, ‘A Comparative Study of Meta- heuristic Algorithms for Solving Quadratic Assignment Problem’, Int. J. Adv. Comput. Sci. Appl., vol. 5, no. 1, 2014, doi: 10.14569/IJACSA.2014.050101

    work page arXiv 2014

  77. [80]

    S. A. Hosseini Baboli, A. Arabkoohsar, and I. Seyedi, ‘Numerical modeling and optimization of pressure drop and heat transfer rate in a polymer fuel cell parallel cooling channel’, J. Braz. Soc. Mech. Sci. Eng., vol. 45, no. 4, p. 201, Apr. 2023, doi: 10.1007/s40430-023-04106-z

    work page doi:10.1007/s40430-023-04106-z 2023

  78. [81]

    R. K. Ahuja, J. B. Orlin, and A. Tiwari, ‘A greedy genetic algorithm for the quadratic assignment problem’, Comput. Oper. Res., vol. 27, no. 10, pp. 917–934, 2000

    work page 2000

  79. [1998]

    17, 2025

    Accessed: Jul. 17, 2025. [Online]. Available: https://books.google.com/books?hl=en&lr=&id=qUUxEAAAQBAJ&oi=fnd&pg=PR1&dq=Bertsek as,+D.+P.+(1998).+Network+optimization:+Continuous+and+discrete+models.+Athena+Scientific. &ots=58tND5ymSQ&sig=FjPC3UE-K9KSoAM0ewjb9I8Yd68

    work page 2025

  80. [2025]

    Available: https://proceedings.neurips.cc/paper/2017/hash/491442df5f88c6aa018e86dac21d3606-Abstract.html

    [Online]. Available: https://proceedings.neurips.cc/paper/2017/hash/491442df5f88c6aa018e86dac21d3606-Abstract.html

    work page 2017

This paper was first reviewed by deepseek-v4-flash on August 5, 2026.