Pith. sign in

REVIEW 3 minor 56 references

Pairwise Multi-marginal Optimal Transport and Embedding for Earth Mover's Distance

T0 review · 0 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The paper establishes that for costs c(x,y)=||x-y||_2^q on R^n, one coupling can keep every pair's expected cost within a finite factor r of the pairwise optimum precisely when n=1 or 0<q<1, and the smallest such r grows as Θ(n^{q/2}) as…

desk verdict A strong, carefully proved paper that introduces a new optimal transport problem and settles the sharp dimension dependence for R^n; worth serious refereeing despite the intricate SPFR machinery. read the letter →

arxiv 1908.01388 v2 pith:EVWX75JN submitted 2019-08-04 math.PR math.OCmath.STstat.TH

Cheuk Ting Li , Venkat Anantharam This is my paper · ORCID
classification math.PRmath.OCmath.STstat.TH MSC 49Q2260G5546B85
keywords pairwisemulti-marginaloptimaltransportearthmover'sdistanceWassersteinPoissonfunctionalrepresentationbi-Lipschitzembeddinglocalitysensitivehashingsnowflakemetric
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

Pairwise multi-marginal optimal transport asks for a single coupling of many probability distributions in which every pair (X_α, X_β) has expected cost within a factor r of the cost of the optimal coupling of just those two distributions. The paper's central theorem is an exact dichotomy for Euclidean power costs: for c(x,y)=||x-y||_2^q, a finite r is possible exactly in dimension one or when 0

What carries the argument

The engine is the sequential Poisson functional representation (SPFR). It builds, for each distribution P, a chain of Poisson-process points indexed by decreasing ball radii: at each scale one picks the earliest point in a Poisson process weighted by the conditional distribution of a noisy observation of P, then moves to the next scale conditioned on that choice. The Poisson matching lemma bounds the probability that two distributions' SPFR outputs differ by at most roughly twice their total variation distance, and the ball-regularity condition (2.3)-(2.4) controls how much nearby centers can distort comparisons of ball masses. The coupling for all distributions is read off as the limit of SPFR outputs as the scale shrinks. This machinery converts the embedding question into a cost-geometry calculation: the ratio r is controlled by the growth of balls, which for Euclidean space gives Ψ=Θ(√n) and hence r=O($n^{{q/2}}$).

What would settle it

For q≥1 and n≥2 the claim is that r*=∞; a concrete check is the family P_k=(δ_{k e_1}+δ_{-k e_1})/2 in $R^{2}$ with Euclidean cost. The proof of Proposition 35 predicts that any coupling must have a pair with ratio growing unboundedly with k, so exhibiting a coupling with uniformly bounded ratios for all k would settle the claim false.

Watch

Extended reading notes

Core claim

For a symmetric cost c, define r*_c(P(X)) as the infimum over couplings of all distributions on X of the largest ratio E[c(X_α,X_β)] / C*_c(P_α,P_β), where C*_c is the ordinary two-marginal optimal transport cost. The paper proves that for X=R^n and c(x,y)=||x-y||_p^q with 1≤p≤2 and 0<q<1, r*_c(P(R^n))=Θ($n^{{q/p}}$), so in the Euclidean case p=2 the optimal universal ratio grows exactly like $n^{{q/2}}$. For n≥2 and q≥1, r*_c(P(R^n))=∞, so no finite universal coupling exists. The paper also shows that the discrete metric on a Polish space admits r*=2, that every finite metric space has r*=O(log|X|), and that ultrametric costs have bounded ratio; the snowflake-metric upper bound reaches r=O(Ψ^q/(1-q)) under a ball-regularity condition on a reference measure.

Load-bearing premise

The upper-bound construction needs a reference measure whose ball masses are regular: two balls of the same radius centered a distance d apart must exchange mass at rate at most Ψ d/w, and this condition is verified for Lebesgue measure on Euclidean space but is required for every finite-r upper bound in the paper.

Editorial extensions

If this is right

  • For c(x,y)=||x-y||_p^q with q<1 and 1≤p≤2, every family of probability distributions on R^n admits a coupling with pairwise ratio O(n^{q/p}), and the optimal ratio is Θ(n^{q/p}).
  • For the discrete metric on a Polish space, every collection of distributions admits a coupling with expected disagreement at most 2d_TV(P,Q), and no smaller universal constant is possible for infinite support.
  • For q≥1 in dimension n≥2, no finite universal coupling exists, so robust or distributed earth-mover-distance algorithms that work for all distributions must restrict the class of distributions or use a different cost.
  • For the grid [0..s]^n under the Euclidean metric, the coupling gives a bi-Lipschitz embedding of the space of grid distributions into L1 with distortion O(√n log s), improving the previously known O(n log s).
  • The same coupling yields robust transport-plan computation: perturbing input distributions by ε changes the output plan by at most rε in the product transport metric.

Reading between the lines

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

  • Editorial inference: the Θ(n^{q/2}) law depends on the ball-regularity constants, so on spaces where volume grows faster, such as some hyperbolic manifolds, the same construction would not yield a finite r; the paper itself leaves that case open.
  • Editorial inference: the SPFR coupling is naturally a locality-sensitive hash: drawing k independent Poisson-realization seeds and averaging c(X_α,X_β) over them estimates the earth mover's distance up to the factor r, making the grid algorithm a concrete candidate for large-scale EMD estimation.
  • Editorial inference: for finite collections of size m small compared with the ambient dimension, Proposition 18's O(log m) bound should combine with the n^{q/p} law to predict which bound dominates for given m and n.
  • Editorial inference: the snowflake threshold suggests that any practical universal coupling for EMD in high dimension must either restrict the family of distributions or use a modified cost such as ||x-y||^q with q<1.
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

0 major / 3 minor

Summary. The paper introduces and analyzes the pairwise multi-marginal optimal transport problem: given a collection of probability distributions, find a coupling in which every pair of marginals has expected cost within a factor r of its individually optimal value. The central result is a sharp dichotomy for Euclidean snowflake costs c(x,y)=||x-y||_2^q: for R^n a finite r exists if and only if n=1 or 0<q<1, and when 0<q<1 the optimal r grows exactly as Θ(n^{q/2}) in dimension. The upper bound is obtained from a new sequential Poisson functional representation (SPFR) construction, Theorem 4, whose hypotheses (2.3)-(2.4) are verified for R^n with Lebesgue measure; the lower bound is proved by cycle constructions and an edge-isoperimetric argument, Theorem 9 and Proposition 35. The paper also contains results for discrete metrics, finite metric spaces, ultrametrics, grids, Riemannian manifolds, algorithmic implementations, and embeddings into L1, including an improvement over Indyk and Thaper from O(n log s) to O(√n log s) for the grid.

Significance. The results are significant: they resolve the dimensional growth rate of the optimal pairwise coupling ratio for the central Euclidean case and establish a clean finiteness dichotomy. The SPFR construction is a genuinely new technique that avoids tree metrics and yields explicit constants, and the lower bounds use independent external results (Naor-Schechtman for the q=1 case and Bollobás-Leader for the isoperimetric step). The paper is unusually complete: the main upper and lower bounds are both developed in detail, the regularity assumptions of Theorem 4 are verified for the Euclidean target space rather than merely assumed there, and the algorithmic and embedding consequences are worked out concretely. I found no circularity: the upper bounds come from an explicit construction and the lower bounds use separate arguments. The presentation is long and the constant-heavy proofs are demanding, but the central claims are well supported.

minor comments (3)
  1. [Sections 5.1 and 5.2, Eqs. (5.8) and (5.11)] The definition of the kernel UB_w appears to contain a sign error: as written, UB_w(x,E)=µ(B_w(x)\E)/µ(B_w(x)) is not a probability measure in E and is incompatible with the total variation computation in (5.15). The subsequent arguments require UB_w(x,E)=µ(B_w(x)∩E)/µ(B_w(x)), i.e. the uniform distribution on B_w(x). The same correction should be applied in Remark 32 and in Algorithm 2, where round*UB_w is used.
  2. [Notation section, page 4] The notation Z≥a := R≥a\Z appears to be a typo: the intended object is the set of integers at least a, i.e. Z∩[a,∞). The printed definition would denote the non-integer reals at least a.
  3. [Appendix E, Eqs. (E.1)-(E.4)] The verification of the SPFR condition for Theorem 4 is dense, and the constant ξ in (E.1) and its use in the likelihood-ratio bound (E.4) are central but not motivated. A short paragraph explaining why i0 is chosen so that (2.4) gives a uniform bound on the ball-volume ratio, and how that feeds into (E.4)-(E.6), would substantially improve readability and verifiability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorem is supported by explicit SPFR constructions and independent lower-bound arguments.

full rationale

The central dichotomy (finite r iff n=1 or 0<q<1) and the matching Θ(n^{q/2}) growth are not obtained by fitting parameters, renaming known results, or assuming the target conclusion. Theorem 4 supplies an upper bound from the explicit sequential Poisson functional representation under the ball-regularity hypotheses (2.3) and (2.4), and the proof of Theorem 6 verifies those hypotheses for R^n with Lebesgue measure, giving a concrete Ψ. The lower bounds are independent of the SPFR machinery: Proposition 7 uses explicit cycle constructions and Theorem 9 uses an external edge-isoperimetric inequality on the discrete torus. The only load-bearing self-citation is the Poisson matching lemma of [21], used through (4.2), Proposition 23 and Lemma 27; that lemma is parameter-free, has stated assumptions that do not include the pairwise-coupling-ratio claim, and is not itself obtained from the present paper's results, so under the given rules it counts as independent support rather than circularity. No equation in the derivation reduces to an input by construction.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

All substantive parameters in the theorem statements (q, p, n, s, Ψ) are variables or geometric quantities, not fitted to data. The hand-tuned constants η and l appear only in the proofs and affect absolute constants, not rates. The central results rely on standard external theorems: the Poisson matching lemma, FRT tree metrics, Bishop-Gromov comparison, Naor-Schechtman non-embeddability, edge-isoperimetric inequalities, and measure-theoretic regularity. The key domain assumption is the ball-regularity condition of Theorem 4, which is verified for the spaces where the main theorems are claimed. No invented physical entities are introduced.

free parameters (2)
  • η = 1.56
    Hand-tuned constant in the finite-metric SPFR proof and Algorithm 1; it only affects the absolute factor 55.7 in Theorem 15, not the O(log|X|) or O(√n log s) rates.
  • l = ceil(10/(3 log(7.555/7.554)))
    Discretization parameter in Theorem 4 used to make the random shift Θ nearly uniform; chosen to absorb a constant in the bound and has no effect on the Θ(n^{q/2}) scaling.
assumptions (6)
  • standard math Poisson matching lemma from Li-Anantharam (arXiv:1812.03616)
    Used as the basis for the universal Poisson coupling and for bounding the Poisson coupling distance by 2 times total variation in Proposition 23 and Theorem 3; accepted from cited prior work.
  • standard math Fakcharoenphol-Rao-Talwar random tree metric approximation
    Used in Theorem 15 and Proposition 18 to obtain O(log n) bounds for finite metric spaces and finite collections of distributions.
  • standard math Bishop-Gromov volume comparison
    Used in Theorem 14 to verify the ball-regularity condition for Riemannian manifolds with Ricci curvature bounded below.
  • standard math Non-embeddability of planar Earth mover distance into L1 (Naor-Schechtman)
    Used in Proposition 7 and equation (9.2) to prove r*=∞ for n≥2, q=1 and to obtain grid lower bounds.
  • standard math Measure-theoretic regularity: Borel probability measures on Polish spaces, existence of regular conditional distributions, and product σ-algebras on X^Z
    Needed for the SPFR measurability arguments, limiting arguments in Definition 25, Lemma 26, and Appendix E.
  • domain assumption Ball-regularity conditions (2.3) and (2.4) on the auxiliary measure µ
    Assumed in Theorem 4 and verified for Lebesgue measure on R^n (Ψ=O(√n)), counting measure on grids, and Riemannian volume under curvature bounds. If violated, the SPFR upper-bound construction is not guaranteed.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Pairwise Multi-marginal Optimal Transport and Embedding for Earth Mover's Distance." pith.science (2026). https://pith.science/paper/EVWX75JN

@misc{pith2026190801388,
  author       = {Pith},
  title        = {Pith review of: Pairwise Multi-marginal Optimal Transport and Embedding for Earth Mover's Distance},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EVWX75JN}},
  note         = {Machine review of arXiv:1908.01388}
}
abstract

We investigate the problem of pairwise multi-marginal optimal transport, that is, given a collection of probability distributions $\{P_\alpha\}$ on a Polish space $\mathcal{X}$, to find a coupling $\{X_\alpha\}$, $X_\alpha\sim P_\alpha$, such that $\mathbf{E}[c(X_\alpha,X_\beta)]\le r\inf_{X\sim P_\alpha,Y\sim P_\beta}\mathbf{E}[c(X,Y)]$ for all $\alpha,\beta$, where $c$ is a cost function and $r\ge1$. In other words, every pair $(X_\alpha,X_\beta)$ has an expected cost at most a factor of $r$ from its lowest possible value. This can be regarded as a locality sensitive hash function for probability distributions, and has applications such as robust and distributed computation of transport plans. It can also be considered as a bi-Lipschitz embedding of the collection of probability distributions into the space of random variables taking values on $\mathcal{X}$. For $c(x,y)=\Vert x-y\Vert_2^q$ on $\mathbb{R}^n$, where $q>0$, we show that a finite $r$ is attainable if and only if either $n=1$ or $0<q<1$. As $n\to\infty$, the growth rate of the smallest possible $r$ is exactly $\Theta(n^{q/2})$ if $0<q<1$. Hence, the metric space of probability distributions on $\mathbb{R}^n$ with finite $q$-th absolute moments, $0<q<1$, with the earth mover's distance (or 1-Wasserstein distance) with respect to the snowflake metric $c(x,y)=\Vert x-y\Vert_2^q$, is bi-Lipschitz embeddable into $L_1$ with distortion $O(n^{q/2})$. If we consider $c(x,y)=\Vert x-y\Vert_2$ (i.e., $q=1$) on the grid $[0..s]^n$ instead of $\mathbb{R}^n$, then $r=O(\sqrt{n}\log s)$ is attainable, which implies the embeddability of the space of probability distributions on $[0..s]^n$ into $L_1$ with distortion $O(\sqrt{n}\log s)$, and improves upon the $O(n\log s)$ result by Indyk and Thaper. The case of the discrete metric cost $c(x,y)=\mathbf{1}\{x\neq y\}$ and more general metric and ultrametric costs are also investigated.

Figures

Figures reproduced from arXiv: 1908.01388 by the authors.

Figure 2.1
Figure 2.1. Log-scale plot of the upper bound (Theorem 6) and lower bound (Proposition 34 and [PITH_FULL_IMAGE:figures/full_fig_p015_2_1.png] view at source ↗
Figure 2.2
Figure 2.2. Log-log plot of the upper bound (Theorem 6) and lower bound (Proposition 34 and Theorem [PITH_FULL_IMAGE:figures/full_fig_p015_2_2.png] view at source ↗
Figure 2.3
Figure 2.3. Log-scale plot of the upper bound (Theorem 6, green wireframe) and lower bound (Propo [PITH_FULL_IMAGE:figures/full_fig_p016_2_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

56 extracted references · 55 canonical work pages

  1. [1]

    Mémoire sur la théorie des déblais et des remblais,

    G. Monge, “Mémoire sur la théorie des déblais et des remblais,”Histoire de l’Académie royale des sciences de Paris, 1781

    work page

  2. [2]

    On the translocation of masses,

    L. V. Kantorovich, “On the translocation of masses,” inDokl. Akad. Nauk. USSR (NS), vol. 37, 1942, pp. 199–201

    work page 1942

  3. [3]

    Duality theorems for marginal problems,

    H. G. Kellerer, “Duality theorems for marginal problems,”Zeitschrift für Wahrscheinlichkeitsthe- orie und verwandte Gebiete, vol. 67, no. 4, pp. 399–432, 1984

    work page 1984

  4. [4]

    Optimal maps for the multidimensional Monge-Kantorovich prob- lem,

    W. Gangbo and A. Święch, “Optimal maps for the multidimensional Monge-Kantorovich prob- lem,”Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, vol. 51, no. 1, pp. 23–45, 1998. 88

    work page 1998

  5. [5]

    Problème de monge pour n probabilités,

    H. Heinich, “Problème de monge pour n probabilités,”Comptes Rendus Mathematique, vol. 334, no. 9, pp. 793–795, 2002

    work page 2002

  6. [6]

    On a class of multidimensional optimal transportation problems,

    G. Carlier, “On a class of multidimensional optimal transportation problems,”Journal of convex analysis, vol. 10, no. 2, pp. 517–530, 2003

    work page 2003

  7. [7]

    Uniqueness and Monge solutions in the multimarginal optimal transportation problem,

    B. Pass, “Uniqueness and Monge solutions in the multimarginal optimal transportation problem,” SIAM Journal on Mathematical Analysis, vol. 43, no. 6, pp. 2758–2775, 2011

    work page 2011

  8. [8]

    On the local structure of optimal measures in the multi-marginal optimal transportation problem,

    ——, “On the local structure of optimal measures in the multi-marginal optimal transportation problem,”Calculus of Variations and Partial Differential Equations, vol. 43, no. 3-4, pp. 529–536, 2012

    work page 2012

Show all 56 references
  1. [9]

    Multi-marginal optimal transport and multi-agent matching problems: uniqueness and structure of solutions,

    ——, “Multi-marginal optimal transport and multi-agent matching problems: uniqueness and structure of solutions,”arXiv preprint arXiv:1210.7372, 2012

    2012 arXiv

  2. [10]

    Similarity estimation techniques from rounding algorithms,

    M. S. Charikar, “Similarity estimation techniques from rounding algorithms,” inProceedings of the thiry-fourth annual ACM symposium on Theory of computing. ACM, 2002, pp. 380–388

    2002

  3. [11]

    Fast image retrieval via embeddings,

    P. Indyk and N. Thaper, “Fast image retrieval via embeddings,” in3rd international workshop on statistical and computational theories of vision, 2003, pp. 1–15

    2003

  4. [12]

    Imagesimilaritysearchwithcompactdatastructures,

    Q.Lv, M.Charikar, andK.Li, “Imagesimilaritysearchwithcompactdatastructures,” in Proceed- ings of the thirteenth ACM international conference on Information and knowledge management. ACM, 2004, pp. 208–217

    2004

  5. [13]

    Efficient sketches for earth-mover distance, with applications,

    A. Andoni, K. Do Ba, P. Indyk, and D. Woodruff, “Efficient sketches for earth-mover distance, with applications,” in2009 50th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2009, pp. 324–330

    2009

  6. [14]

    Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields,

    J. Kleinberg and E. Tardos, “Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields,”Journal of the ACM (JACM), vol. 49, no. 5, pp. 616–639, 2002

    2002

  7. [15]

    Approx- imate classification via earthmover metrics,

    A. Archer, J. Fakcharoenphol, C. Harrelson, R. Krauthgamer, K. Talwar, and É. Tardos, “Approx- imate classification via earthmover metrics,” inProceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2004, pp....

    2004

  8. [16]

    Nonembeddability theorems via Fourier analysis,

    S. Khot and A. Naor, “Nonembeddability theorems via Fourier analysis,”Mathematische Annalen, vol. 334, no. 4, pp. 821–852, 2006

    2006

  9. [17]

    Planar earthmover is not inL1,

    A. Naor and G. Schechtman, “Planar earthmover is not inL1,”SIAM Journal on Computing, vol. 37, no. 3, pp. 804–826, 2007

    2007

  10. [18]

    A tight bound on approximating arbitrary metrics by tree metrics,

    J. Fakcharoenphol, S. Rao, and K. Talwar, “A tight bound on approximating arbitrary metrics by tree metrics,”Journal of Computer and System Sciences, vol. 69, no. 3, pp. 485–497, 2004

    2004

  11. [19]

    Pairwise optimal coupling of multiple random variables,

    O. Angel and Y. Spinka, “Pairwise optimal coupling of multiple random variables,”arXiv preprint arXiv:1903.00632, 2019

    1903 arXiv

  12. [20]

    Strong functional representation lemma and applications to coding theorems,

    C. T. Li and A. El Gamal, “Strong functional representation lemma and applications to coding theorems,”IEEE Transactions on Information Theory, vol. 64, no. 11, pp. 6967–6978, Nov 2018

    2018

  13. [21]

    A unified framework for one-shot achievability via the Poisson matching lemma,

    C. T. Li and V. Anantharam, “A unified framework for one-shot achievability via the Poisson matching lemma,”arXiv preprint arXiv:1812.03616, 2018. 89

    2018 arXiv

  14. [22]

    Plongements lipschitziens dansRn,

    P. Assouad, “Plongements lipschitziens dansRn,”Bulletin de la Société Mathématique de France, vol. 111, pp. 429–448, 1983

    1983

  15. [23]

    Better embeddings for planar earth-mover distance over sparse sets,

    A. Bačkurs and P. Indyk, “Better embeddings for planar earth-mover distance over sparse sets,” in Proceedings of the thirtieth annual symposium on Computational geometry. ACM, 2014, p. 280

    2014

  16. [24]

    Sur une nouvelle méthode pour la détermination des intégrales multiples,

    P. G. L. Dirichlet, “Sur une nouvelle méthode pour la détermination des intégrales multiples,” Journal de Mathématiques Pures et Appliquées, vol. 4, pp. 164–168, 1839

  17. [25]

    Volumes of generalized unit balls,

    X. Wang, “Volumes of generalized unit balls,”Mathematics Magazine, vol. 78, no. 5, pp. 390–395, 2005

    2005

  18. [26]

    Last and M

    G. Last and M. Penrose,Lectures on the Poisson process. Cambridge University Press, 2017, vol. 7

    2017

  19. [27]

    Burago, I

    D. Burago, I. D. Burago, Y. Burago, S. A. Ivanov, and S. Ivanov,A course in metric geometry. American Mathematical Soc., 2001, vol. 33

    2001

  20. [28]

    Approximating snowflake metrics by trees,

    W. Leeb, “Approximating snowflake metrics by trees,”Applied and Computational Harmonic Analysis, vol. 45, no. 2, pp. 405–424, 2018

    2018

  21. [29]

    S. T. Rachev and L. Rüschendorf,Mass Transportation Problems: Volume I: Theory. Springer Science & Business Media, 1998, vol. 1

    1998

  22. [30]

    A geometric study of Wasserstein spaces: ultrametrics,

    B. R. Kloeckner, “A geometric study of Wasserstein spaces: ultrametrics,”Mathematika, vol. 61, no. 1, pp. 162–178, 2015

    2015

  23. [31]

    Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems,

    M. Iwasa, H. Saito, and T. Matsui, “Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems,”Discrete Applied Mathematics, vol. 157, no. 9, pp. 2078–2088, 2009

    2009

  24. [32]

    Image labeling based on graphical mod- els using Wasserstein messages and geometric assignment,

    R. Hühnerbein, F. Savarino, F. Åström, and C. Schnörr, “Image labeling based on graphical mod- els using Wasserstein messages and geometric assignment,”SIAM Journal on Imaging Sciences, vol. 11, no. 2, pp. 1317–1362, 2018

    2018

  25. [33]

    Fast approximate energy minimization via graph cuts,

    Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via graph cuts,” in Proceedings of the Seventh IEEE International Conference on Computer Vision, vol. 1. IEEE, 1999, pp. 377–384

    1999

  26. [34]

    Fast approximate energy minimization via graph cuts,

    ——, “Fast approximate energy minimization via graph cuts,”IEEE Transactions on pattern analysis and machine intelligence, vol. 23, no. 11, pp. 1222–1239, 2001

    2001

  27. [35]

    On dependent randomized rounding algorithms,

    D. Bertsimas, C. Teo, and R. Vohra, “On dependent randomized rounding algorithms,”Operations Research Letters, vol. 24, no. 3, pp. 105–114, 1999

    1999

  28. [36]

    A unified approach to the change of resolution: Space and gray-level,

    S. Peleg, M. Werman, and H. Rom, “A unified approach to the change of resolution: Space and gray-level,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, no. 7, pp. 739–742, 1989

    1989

  29. [37]

    Optimal mass transport for registration and warping,

    S. Haker, L. Zhu, A. Tannenbaum, and S. Angenent, “Optimal mass transport for registration and warping,”International Journal of computer vision, vol. 60, no. 3, pp. 225–240, 2004

    2004

  30. [38]

    Matching for teams,

    G. Carlier and I. Ekeland, “Matching for teams,”Economic theory, vol. 42, no. 2, pp. 397–418, 2010

    2010

  31. [39]

    Hedonic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness,

    P.-A. Chiappori, R. J. McCann, and L. P. Nesheim, “Hedonic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness,”Economic Theory, vol. 42, no. 2, pp. 317–354, 2010. 90

    2010

  32. [40]

    J. F. C. Kingman,Poisson Processes. Oxford University Press, 1993

    1993

  33. [41]

    Hyperplane projections of the unit ball of𝓁n p,

    F. Barthe and A. Naor, “Hyperplane projections of the unit ball of𝓁n p,”Discrete & Computational Geometry, vol. 27, no. 2, pp. 215–226, 2002

    2002

  34. [42]

    Problems and solutions. subsection: The volume of the intersection of a cube and a ball in N-space. two solutions by Bernd Tibken and Denis Constales,

    C. Rousseau and O. Ruehr, “Problems and solutions. subsection: The volume of the intersection of a cube and a ball in N-space. two solutions by Bernd Tibken and Denis Constales,”SIAM Review, vol. 39, pp. 779–786, 1997

    1997

  35. [43]

    Petersen,Riemannian Geometry

    P. Petersen,Riemannian Geometry. Springer, 2016

    2016

  36. [44]

    Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathe- matica

    S. Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathe- matica. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1991

    1991

  37. [45]

    A linear-time algorithm for the longest path problem in rectangular grid graphs,

    F. Keshavarz-Kohjerdi, A. Bagheri, and A. Asgharian-Sardroud, “A linear-time algorithm for the longest path problem in rectangular grid graphs,”Discrete Applied Mathematics, vol. 160, no. 3, pp. 210–217, 2012

    2012

  38. [46]

    On Lipschitz embedding of finite metric spaces in Hilbert space,

    J. Bourgain, “On Lipschitz embedding of finite metric spaces in Hilbert space,”Israel Journal of Mathematics, vol. 52, no. 1-2, pp. 46–52, 1985

    1985

  39. [47]

    The geometry of graphs and some of its algorithmic applications,

    N. Linial, E. London, and Y. Rabinovich, “The geometry of graphs and some of its algorithmic applications,”Combinatorica, vol. 15, no. 2, pp. 215–245, 1995

    1995

  40. [48]

    A graph-theoretic game and its application to the k-server problem,

    N. Alon, R. M. Karp, D. Peleg, and D. West, “A graph-theoretic game and its application to the k-server problem,”SIAM Journal on Computing, vol. 24, no. 1, pp. 78–100, 1995

    1995

  41. [49]

    Probabilistic approximation of metric spaces and its algorithmic applications,

    Y. Bartal, “Probabilistic approximation of metric spaces and its algorithmic applications,” in Proceedings of 37th Conference on Foundations of Computer Science. IEEE, 1996, pp. 184–193

    1996

  42. [50]

    Snowflake universality of Wasserstein spaces,

    A. Andoni, A. Naor, and O. Neiman, “Snowflake universality of Wasserstein spaces,” inAnnales Scientifiques de l’Ecole Normale Superieure, vol. 51, no. 3. Societe Mathematique de France, 2018, pp. 657–700

    2018

  43. [51]

    Lois stables et espacesLp,

    J. Bretagnolle, D. Dacunha Castelle, and J.-L. Krivine, “Lois stables et espacesLp,” inAnnales de l’IHP Probabilités et statistiques, vol. 2, no. 3, 1966, pp. 231–259

    1966

  44. [52]

    Reducibility among combinatorial problems,

    R. M. Karp, “Reducibility among combinatorial problems,” inComplexity of computer computa- tions. Springer, 1972, pp. 85–103

    1972

  45. [53]

    V. I. Bogachev,Measure theory. Springer-Verlag Berlin Heidelberg, 2007, vol. 1

    2007

  46. [54]

    Edge-isoperimetric inequalities in the grid,

    B. Bollobás and I. Leader, “Edge-isoperimetric inequalities in the grid,”Combinatorica, vol. 11, no. 4, pp. 299–314, 1991

    1991

  47. [55]

    Jost, Riemannian Geometry and Geometric Analysis

    J. Jost, Riemannian Geometry and Geometric Analysis. Berlin Heidelberg: Springer-Verlag, 2002

    2002

  48. [56]

    A2k-competitive algorithm for the circle,

    R. M. Karp, “A2k-competitive algorithm for the circle,”Manuscript, August 1989. 91

    1989

Pith tools

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