Pith. sign in

REVIEW 2 major objections 5 minor 32 references

Optimal Multimarginal Schr\"odinger Bridge: Minimum Spanning Tree over Measure-valued Vertices

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read This paper establishes that the optimal multimarginal Schrödinger bridge over a given set of probability measures is the minimum spanning tree of the complete graph whose edge weights are pairwise bridge costs plus endpoint entropies.

desk verdict The MST reduction for optimal multimarginal Schrödinger bridge graph selection is a clean, useful observation, but the proof of the key tree decomposition is flawed as written and should defer to Haasler et al.; the central claim is likely correct and deserves a serious referee. read the letter →

arxiv 2509.10626 v1 pith:KUIORLET submitted 2025-09-12 cs.LG cs.AImath.OCstat.ML

Georgiy A. Bondar , Abhishek Halder This is my paper · ORCID
classification cs.LGcs.AImath.OCstat.ML MSC 49Q2205C0590C27
keywords multimarginalSchrödingerbridgeminimumspanningtreeentropicoptimaltransporttree-structuredcouplingSinkhornalgorithmmeasure-valuedverticesgraph-structuredcostdecomposition
verification ladder T0 review T1 audit T2 compute T3 formal

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 asks a design question: when several probability measures must be joined by a correlation structure, which graph among all connected options makes the entropy-regularized transport problem optimal? It claims the optimal graph is always a tree, and that the best tree is the minimum spanning tree of a complete graph whose edge weights are each pair's bimarginal Schrödinger bridge value plus the entropies of the two endpoints. If true, a combinatorial search over all tree structures becomes two standard computations: solve pairwise bridges, then run a textbook minimum spanning tree algorithm. The result makes the optimal correlation structure computationally accessible; for equal support sizes the total cost is quasilinear in the number of measures and quadratic in the support size.

What carries the argument

The load-bearing machinery is the tree-decomposition identity for tree-structured MSBs: $D_{\mathrm{KL}}(M^{\mathrm{opt}}_T \| K) = \sum_{(\sigma_1,\sigma_2)\in E} \mathrm{SB}_\eta(\mu_{\sigma_1},\mu_{\sigma_2}) + \sum_{\sigma\in J_sK} (\deg(\mu_\sigma)-1) H(\mu_\sigma)$. This identity makes the global objective additive over edges, which reduces the combinatorial search over $s^{s-2}$ spanning trees to a polynomial-time minimum spanning tree computation. It is established through a cutting lemma that splits a tree at a non-leaf vertex into two independent subtree problems, so that the full optimal coupling factorizes as the product of the two subtree couplings divided by the shared marginal.

What would settle it

Solve a tree-structured MSB for four measures by direct multimarginal Sinkhorn on a known tree, compute the right-hand side of the decomposition identity from the pairwise optimal bridge values and the vertex entropies, and compare the two: any difference beyond solver tolerance would show the identity is false. A more direct check would take a non-tree-structured coupling with prescribed marginals and verify whether it equals the product of its two subtree projections divided by the shared marginal.

Watch

Extended reading notes

Core claim

The central claim is the equivalence between the optimal MSB problem and a minimum spanning tree problem. Any cycle in the graph can be removed without changing the coupling constraints while reducing the ground cost, so the optimal graph is a spanning tree. The tree-decomposition identity then writes the objective of any tree-structured MSB as a sum over edges of pairwise bridge values plus a sum over vertices of (degree minus one) times entropy; absorbing vertex entropies into edge weights $g_{\sigma_1\sigma_2} = \mathrm{SB}_\eta(\mu_{\sigma_1},\mu_{\sigma_2}) + H(\mu_{\sigma_1}) + H(\mu_{\sigma_2})$ turns the tree cost into an additive sum of edge weights minus a constant independent of the tree. Minimizing that sum over all spanning trees is exactly the minimum spanning tree problem, and the proposed two-step algorithm, which computes all pairwise bridges and then the MST, returns the optimal graph structure.

Load-bearing premise

The entire MST reduction rests on the tree-decomposition identity: for any tree-structured MSB, the optimal coupling factorizes along the tree so that the full objective equals a sum of pairwise bridge costs plus vertex entropy terms, an identity the paper takes from earlier work and sketches via a factorization valid for tree-structured couplings.

Editorial extensions

If this is right

  • The optimal correlation graph for any MSB over fixed measures never contains cycles; a cycle only adds positive ground cost without relaxing any marginal constraint.
  • The objective of any tree-structured MSB can be evaluated from bimarginal bridge values and vertex entropies alone, without constructing the full joint coupling tensor.
  • Solving the optimal MSB costs one bimarginal Sinkhorn run per pair plus one MST computation; for equal supports the stated complexity is $O(s^2 n^2 \|C\|_\infty^2 \log n / \varepsilon^2)$, and the pairwise computations can be parallelized.
  • When all edge weights $g_{\sigma_1\sigma_2}$ are distinct, the optimal graph structure is unique.
  • The same pipeline supports most-likely spatio-temporal reconstruction from unordered snapshots; in the paper's video experiment, the recovered optimal tree was a path matching the true frame order.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: The edge-weight formula defines an implicit dissimilarity $d(\mu_\sigma,\mu_{\sigma'})=\mathrm{SB}_\eta(\mu_\sigma,\mu_{\sigma'})+H(\mu_\sigma)+H(\mu_{\sigma'})$ on probability measures; testing whether this function satisfies a relaxed triangle inequality could connect the result to hierarchical clustering and to the Euclidean MST literature the paper cites.
  • Inference: The structural parallel with Chow-Liu tree approximation, which the paper notes in a remark, suggests a broader reading: the optimal MSB tree is the minimum-cost dependency tree for given marginals under entropic transport cost, and one could test empirically how this tree compares with the Chow-Liu tree as the regularization parameter varies.
  • Inference: The path recovery in the unordered-frame experiment points to a general unsupervised temporal-ordering application; a systematic test would generate synthetic snapshot sequences with known ground-truth ordering and check whether the optimal MSB tree reconstructs the temporal path.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper studies the multimarginal Schr\"odinger bridge (MSB) when the correlation graph is not fixed a priori. It formulates the problem of minimizing the MSB cost over all connected graphs on a given set of measure-valued vertices and claims that this problem is equivalent to a minimum spanning tree (MST) problem. The proposed reduction is: an optimal graph is a spanning tree (Proposition 1); a tree-structured MSB decomposes into pairwise Schr\"odinger bridge costs plus vertex entropy terms (Proposition 2 and Corollary 1, Eq. (19)); and this yields edge weights g_{\sigma_1\sigma_2} = SB_\eta(\mu_{\sigma_1},\mu_{\sigma_2}) + H(\mu_{\sigma_1}) + H(\mu_{\sigma_2}) in Eq. (20), reducing problem (11) to the MST problem (22). Algorithm 1 implements this by computing all pairwise SB values and then applying a standard MST algorithm. The paper reports a complexity analysis and two numerical experiments, one with Gaussian-mixture vertices and one with video-frame reconstruction.

Significance. If the central reduction is correct, it is a conceptually clean and practically valuable result: it replaces a combinatorial search over an exponential number of graph structures with pairwise Schr\"odinger bridge computations and a polynomial-time MST solve. The paper also draws a useful analogy to Chow-Liu trees and demonstrates the idea on small numerical examples. The main theoretical contribution is, however, currently not fully established in the text: the proof of the tree-decomposition identity contains a factorization step that is only valid for tree-Markov couplings, not for arbitrary couplings in \Pi(V). Since that identity is exactly what makes the edge weights additive, the correctness of the reduction depends on it. The manuscript cites the external result [5, Prop. 3.4] as the source of the decomposition, so the gap is likely repairable, but it must be properly addressed before the paper can be accepted.

major comments (2)
  1. [III-A, Proposition 2, Eqs. (15) and (19)] The proof of Proposition 2 is not valid as written. It begins with the factorization [M_iV] = [proj_{V1}(M)]/(\mu_\sigma) \cdot (\mu_\sigma) \cdot [proj_{V2}(M)]/(\mu_\sigma) for any M in \Pi(V). This identity is exactly the tree-Markov conditional-independence property and is false for a general joint distribution with the prescribed marginals. Consequently, the rewriting of \Pi(V) as a product of projections and the subsequent splitting of the objective in Eq. (16) do not apply to arbitrary feasible M. Since Corollary 1's Eq. (19), and hence the additive edge weights in Eq. (20), depend on this decomposition, the central MST reduction is not established by the proof given in the text. The authors correctly cite Haasler et al. [5, Prop. 3.4] as an external source of a tree-decomposition result; the manuscript should either quote that result explicitly and show how it yields (15) and (19), or provide a proof that first characterizes the minimizer as tree-Markov and then performs the factorization within that restricted class.
  2. [II, Proposition 1 and III-B, Theorem 1] The statement that the optimal graph G_opt is a spanning tree, and the equality T_opt = G_opt in Theorem 1, are overstrong. If an edge has zero cost, removing it from a cycle leaves the objective unchanged, so a graph containing cycles can be optimal. The valid conclusion is that there exists an optimal spanning tree and that any minimum spanning tree over the nonnegative weights attains the optimal value in (11); Algorithm 1 solves the problem in value, but not every optimum is necessarily a tree. The proof of Proposition 1 uses a strict decrease in the cost tensor that need not hold when edge costs vanish.
minor comments (5)
  1. [III-A, Eq. (20) and Remark 1] The edge weight g_{\sigma_1\sigma_2} is written as a sum of an SB cost and two entropies; the base of the logarithm in H and in the KL divergence should be stated explicitly, since the numerical values and the comparison with mutual information in Remark 1 depend on that convention.
  2. [IV-A, paragraph after Table I] The sentence 'the proposed Algorithm 1 took \approx0.226 seconds to construct the optimal tree, along with all other possible trees' is unclear; it presumably means that all pairwise SB values were computed once in that time. Please clarify what was measured.
  3. [IV-A, Table I] The table caption says the costs were 'computed both globally and edgewise,' but the two columns are simply labeled 'Cost (11)' and 'Cost (21)'. It would help to state explicitly that the first column evaluates the tree-structured MSB directly and the second evaluates the additive expression from Eq. (21).
  4. [III-C, Complexity] The translation from the \varepsilon-accurate Sinkhorn complexity to the \eta dependence is terse; since \eta = \varepsilon/(4\log n) is inserted inside a big-O expression, the constant and the validity of this substitution should be stated more carefully, for instance by writing the bound as a function of \eta rather than by direct replacement inside the \varepsilon-bound.
  5. [II, Example 1] The sentence 'The only feasible coupling is a Dirac measure that equals to the product of the given Dirac measures' is correct in the discrete setting used here, but it would be clearer to note that the entropy term vanishes because the coupling is deterministic, not because the marginals are Dirac.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the MST reduction rests on an external decomposition theorem, and no parameter or edge weight is fitted to the target global optimum.

full rationale

The paper's central claim is that the optimal MSB problem (11) is equivalent to an MST problem with edge weights (20). The load-bearing step is the tree decomposition in Proposition 2 and Corollary 1, specifically equation (19), which expresses the tree-structured MSB cost as a sum of pairwise SB values plus vertex entropy terms. This decomposition is attributed to an independent external result, Haasler et al. [5, Prop. 3.4], and the authors of that result do not overlap with the present authors. The edge weights g_{\sigma_1\sigma_2} are computed from bimarginal SB problems and entropies of the input measures; no parameter is fitted to the global MSB cost, and the MST optimization over these weights is not definitionally identical to problem (11). The paper's own proof of Proposition 2 does contain a soundness gap: it applies a tree-Markov conditional-independence factorization to arbitrary couplings in \Pi(V), which is not valid for general M. However, that is a proof deficiency, not circularity, and the underlying statement is independently sourced rather than being presupposed by the paper's own definitions. The self-citations in the reference list ([8], [9]) appear only in the related-work discussion and are not load-bearing for the derivation. Therefore, the derivation chain does not reduce to its inputs by construction, and no significant circularity is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the external decomposition theorem [5, Prop. 3.4]; the paper's own proof of that theorem contains a gap. The regularization eta and the Sinkhorn accuracy epsilon are inputs, not fitted parameters. No new entities are introduced.

assumptions (4)
  • domain assumption The tree-structured MSB decomposition (Haasler et al. [5, Prop. 3.4]) holds: D_KL(M_opt_T || K) = sum over edges SB_eta + sum over vertices (degree - 1) H(mu).
    The paper cites [5] for this result, but its own proof of Proposition 2 is invalid as written because it assumes a tree-Markov factorization for arbitrary couplings.
  • domain assumption Ground cost tensors C are elementwise nonnegative, so deleting an edge never increases the MSB cost.
    Used in Proposition 1 and the reduction to spanning trees; stated in the problem setup.
  • standard math The bimarginal Sinkhorn recursion converges to the unique solution of each edge SB problem.
    Standard result cited from [11]-[13] and [27].
  • standard math Standard MST algorithms (Prim, Boruvka) compute the minimum spanning tree of the complete weighted graph.
    Classical algorithms, cited in [20].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Multimarginal Schr\"odinger Bridge: Minimum Spanning Tree over Measure-valued Vertices." pith.science (2026). https://pith.science/paper/KUIORLET

@misc{pith2026250910626,
  author       = {Pith},
  title        = {Pith review of: Optimal Multimarginal Schr\"odinger Bridge: Minimum Spanning Tree over Measure-valued Vertices},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KUIORLET}},
  note         = {Machine review of arXiv:2509.10626}
}
read the original abstract

The Multimarginal Schr\"odinger Bridge (MSB) finds the optimal coupling among a collection of random vectors with known statistics and a known correlation structure. In the MSB formulation, this correlation structure is specified \emph{a priori} as an undirected connected graph with measure-valued vertices. In this work, we formulate and solve the problem of finding the optimal MSB in the sense we seek the optimal coupling over all possible graph structures. We find that computing the optimal MSB amounts to solving the minimum spanning tree problem over measure-valued vertices. We show that the resulting problem can be solved in two steps. The first step constructs a complete graph with edge weight equal to a sum of the optimal value of the corresponding bimarginal SB and the entropies of the endpoints. The second step solves a standard minimum spanning tree problem over that complete weighted graph. Numerical experiments illustrate the proposed solution.

Figures

Figures reproduced from arXiv: 2509.10626 by the authors.

Figure 1
Figure 1. The MST (solid lines) of a complete weighted [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. With the s = 5 Dirac delta measures µσ = δxσ , xσ ∈ R 2 ∀σ ∈ JsK as above, and with the Euclidean distance as the ground cost, the T opt (with solid edges) is a star. A. Tree Decomposition Given a tree T = (V, E) over the vertex set V = {µσ}σ∈JsK , we would like to evaluate the objective of (11) – i.e., the tree-structured MSB – as a sum over the tree’s constituent edges. A key result of Haasler et al. [5, Prop. 3.4… view at source ↗
Figure 3
Figure 3. The optimal MSB graph structure for the numerical [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The optimal MSB graph structure for the numerical experiment in Sec. IV-B. [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

32 extracted references · 30 canonical work pages

  1. [1]

    Multi-marginal optimal transport: theory and applications,

    B. Pass, “Multi-marginal optimal transport: theory and applications,” ESAIM: Mathematical Modelling and Numerical Analysis, vol. 49, no. 6, pp. 1771–1790, 2015

    work page 2015

  2. [2]

    Deep momentum multi-marginal Schr ¨odinger bridge,

    T. Chen, G.-H. Liu, M. Tao, and E. Theodorou, “Deep momentum multi-marginal Schr ¨odinger bridge,”Advances in Neural Information Processing Systems, vol. 36, pp. 57 058–57 086, 2023

    work page 2023

  3. [3]

    Multi-marginal Schr¨odinger bridges with iterative reference refinement,

    Y . Shen, R. Berlinghieri, and T. Broderick, “Multi-marginal Schr¨odinger bridges with iterative reference refinement,” inInterna- tional Conference on Artificial Intelligence and Statistics. PMLR, 2025, pp. 3817–3825

    work page 2025

  4. [4]

    Multi-marginal optimal transport using partial information with applications in robust localization and sensor fusion,

    F. Elvander, I. Haasler, A. Jakobsson, and J. Karlsson, “Multi-marginal optimal transport using partial information with applications in robust localization and sensor fusion,”Signal Processing, vol. 171, p. 107474, 2020

    work page 2020

  5. [5]

    Multimarginal optimal transport with a tree-structured cost and the Schr ¨odinger bridge problem,

    I. Haasler, A. Ringh, Y . Chen, and J. Karlsson, “Multimarginal optimal transport with a tree-structured cost and the Schr ¨odinger bridge problem,”SIAM Journal on Control and Optimization, vol. 59, no. 4, pp. 2428–2453, 2021

    work page 2021

  6. [6]

    Tree-based diffusion Schr¨odinger bridge with applications to Wasserstein barycen- ters,

    M. Noble, V . De Bortoli, A. Doucet, and A. Durmus, “Tree-based diffusion Schr¨odinger bridge with applications to Wasserstein barycen- ters,”Advances in Neural Information Processing Systems, vol. 36, pp. 55 193–55 236, 2023

    work page 2023

  7. [7]

    Oh snapmmd! forecasting stochastic dynamics beyond the Schr ¨odinger bridge’s end,

    R. Berlinghieri, Y . Shen, J. Jiang, and T. Broderick, “Oh snapmmd! forecasting stochastic dynamics beyond the Schr ¨odinger bridge’s end,” arXiv preprint arXiv:2505.16082, 2025

    arXiv 2025

  8. [8]

    Path structured multimarginal Schr ¨odinger bridge for probabilistic learning of hardware resource usage by control software,

    G. A. Bondar, R. Gifford, L. T. X. Phan, and A. Halder, “Path structured multimarginal Schr ¨odinger bridge for probabilistic learning of hardware resource usage by control software,” in2024 American Control Conference (ACC). IEEE, 2024, pp. 4693–4698

    work page 2024

Show all 32 references
  1. [9]

    Stochas- tic learning of computational resource usage as graph-structured multi- marginal Schr ¨odinger bridge,

    G. A. Bondar, R. Gifford, L. Thi Xuan Phan, and A. Halder, “Stochas- tic learning of computational resource usage as graph-structured multi- marginal Schr ¨odinger bridge,”IEEE Transactions on Control Systems Technology, vol. 33, no. 5, pp. 1835–1850, 2025

    2025

  2. [10]

    Multi-marginal Schr¨odinger bridges,

    Y . Chen, G. Conforti, T. T. Georgiou, and L. Ripani, “Multi-marginal Schr¨odinger bridges,” inInternational Conference on Geometric Sci- ence of Information. Springer, 2019, pp. 725–732. 8The timestamps for the frames are{0.166,0.233,0.333,0.666,0.866} seconds, forσ= 1,2,3,4,...

    2019

  3. [11]

    It- erative Bregman projections for regularized transportation problems,

    J.-D. Benamou, G. Carlier, M. Cuturi, L. Nenna, and G. Peyr ´e, “It- erative Bregman projections for regularized transportation problems,” SIAM Journal on Scientific Computing, vol. 37, no. 2, pp. A1111– A1138, 2015

    2015

  4. [12]

    An optimal transport approach for the Schr¨odinger bridge problem and convergence of Sinkhorn algorithm,

    S. D. Marino and A. Gerolin, “An optimal transport approach for the Schr¨odinger bridge problem and convergence of Sinkhorn algorithm,” Journal of Scientific Computing, vol. 85, no. 2, p. 27, 2020

    2020

  5. [13]

    On the linear convergence of the multimarginal Sinkhorn algorithm,

    G. Carlier, “On the linear convergence of the multimarginal Sinkhorn algorithm,”SIAM Journal on Optimization, vol. 32, no. 2, pp. 786– 794, 2022

    2022

  6. [14]

    On the complexity of approximating multimarginal optimal transport,

    T. Lin, N. Ho, M. Cuturi, and M. I. Jordan, “On the complexity of approximating multimarginal optimal transport,”Journal of Machine Learning Research, vol. 23, no. 65, pp. 1–43, 2022

    2022

  7. [15]

    Polynomial-time algorithms for multimarginal optimal transport problems with structure,

    J. M. Altschuler and E. Boix-Adsera, “Polynomial-time algorithms for multimarginal optimal transport problems with structure,”Mathemat- ical Programming, vol. 199, no. 1, pp. 1107–1178, 2023

    2023

  8. [16]

    Multi- marginal optimal transport and probabilistic graphical models,

    I. Haasler, R. Singh, Q. Zhang, J. Karlsson, and Y . Chen, “Multi- marginal optimal transport and probabilistic graphical models,”IEEE Transactions on Information Theory, vol. 67, no. 7, pp. 4647–4668, 2021

    2021

  9. [17]

    Understanding belief propagation and its generalizations,

    J. S. Yedidia, W. T. Freeman, and Y . Weiss, “Understanding belief propagation and its generalizations,”Exploring artificial intelligence in the new millennium, vol. 8, no. 236-239, pp. 0018–9448, 2003

    2003

  10. [18]

    On the complexity of the optimal transport problem with graph-structured cost,

    J. Fan, I. Haasler, J. Karlsson, and Y . Chen, “On the complexity of the optimal transport problem with graph-structured cost,” inInternational conference on artificial intelligence and statistics. PMLR, 2022, pp. 9147–9165

    2022

  11. [19]

    Optimal trees,

    T. L. Magnanti and L. A. Wolsey, “Optimal trees,”Handbooks in operations research and management science, vol. 7, pp. 503–615, 1995

    1995

  12. [20]

    An optimal minimum spanning tree algorithm,

    S. Pettie and V . Ramachandran, “An optimal minimum spanning tree algorithm,”Journal of the ACM (JACM), vol. 49, no. 1, pp. 16–34, 2002

    2002

  13. [21]

    Closest-point problems,

    M. I. Shamos and D. Hoey, “Closest-point problems,” in16th Annual Symposium on Foundations of Computer Science (sfcs 1975). IEEE, 1975, pp. 151–162

    1975

  14. [22]

    Growth rates of Euclidean minimal spanning trees with power weighted edges,

    J. M. Steele, “Growth rates of Euclidean minimal spanning trees with power weighted edges,”The Annals of Probability, vol. 16, no. 4, pp. 1767–1787, 1988

    1988

  15. [23]

    Euclidean minimum spanning trees and bichromatic closest pairs,

    P. K. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, “Euclidean minimum spanning trees and bichromatic closest pairs,” inProceedings of the sixth annual symposium on Computational geometry, 1990, pp. 203–210

    1990

  16. [24]

    A theorem on trees,

    A. Cayley, “A theorem on trees,”Quart. J. Math., vol. 23, pp. 376–378, 1878

  17. [25]

    Approximating discrete probability distributions with dependence trees,

    C. Chow and C. Liu, “Approximating discrete probability distributions with dependence trees,”IEEE transactions on Information Theory, vol. 14, no. 3, pp. 462–467, 1968

    1968

  18. [26]

    T. M. Cover and J. A. Thomas,Elements of information theory. John Wiley & Sons, 1991

    1991

  19. [27]

    Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn’s algorithm,

    P. Dvurechensky, A. Gasnikov, and A. Kroshnin, “Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn’s algorithm,” inInternational conference on machine learning. PMLR, 2018, pp. 1367–1376

    2018

  20. [28]

    Near-linear time ap- proximation algorithms for optimal transport via Sinkhorn iteration,

    J. Altschuler, J. Niles-Weed, and P. Rigollet, “Near-linear time ap- proximation algorithms for optimal transport via Sinkhorn iteration,” Advances in neural information processing systems, vol. 30, 2017

    2017

  21. [29]

    Fibonacci heaps and their uses in improved network optimization algorithms,

    M. L. Fredman and R. E. Tarjan, “Fibonacci heaps and their uses in improved network optimization algorithms,”Journal of the ACM (JACM), vol. 34, no. 3, pp. 596–615, 1987

    1987

  22. [30]

    Spanning trees and spanners,

    D. Eppstein, “Spanning trees and spanners,”Handbook of Computa- tional Geometry, pp. 425–461, 2000

    2000

  23. [31]

    T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,Introduction to Algorithms, 3rd ed. The MIT Press, 2009

    2009

  24. [32]

    Movie gen: A cast of media foundation models,

    The Movie Gen team @ Meta, “Movie gen: A cast of media foundation models,” https://ai.meta.com/static-resource/ movie-gen-research-paper, accessed: 2025-09-10

    2025

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.