{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,27]],"date-time":"2025-11-27T06:43:01Z","timestamp":1764225781554,"version":"3.37.3"},"reference-count":93,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T00:00:00Z","timestamp":1660608000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T00:00:00Z","timestamp":1660608000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1122374"],"award-info":[{"award-number":["1122374"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"TwoSigma PhD fellowship"},{"name":"National Science Foundation","award":["1122374"],"award-info":[{"award-number":["1122374"]}]},{"name":"Siebel PhD Fellowship"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,5]]},"abstract":"Abstract<\/jats:title>Multimarginal Optimal Transport (MOT) has attracted significant interest due to applications in machine learning, statistics, and the sciences. However, in most applications, the success of MOT is severely limited by a lack of efficient algorithms. Indeed, MOT in general requires exponential time in the number of marginals k<\/jats:italic> and their support sizes n<\/jats:italic>. This paper develops a general theory about what \u201cstructure\u201d makes MOT solvable in $$\\mathrm {poly}(n,k)$$<\/jats:tex-math>\n \n poly<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. We develop a unified algorithmic framework for solving MOT in $$\\mathrm {poly}(n,k)$$<\/jats:tex-math>\n \n poly<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time by characterizing the structure that different algorithms require in terms of simple variants of the dual feasibility oracle. This framework has several benefits. First, it enables us to show that the Sinkhorn algorithm, which is currently the most popular MOT algorithm, requires strictly more structure than other algorithms do to solve MOT in $$\\mathrm {poly}(n,k)$$<\/jats:tex-math>\n \n poly<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time. Second, our framework makes it much simpler to develop $$\\mathrm {poly}(n,k)$$<\/jats:tex-math>\n \n poly<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time algorithms for a given MOT problem. In particular, it is necessary and sufficient to (approximately) solve the dual feasibility oracle\u2014which is much more amenable to standard algorithmic techniques. We illustrate this ease-of-use by developing $$\\mathrm {poly}(n,k)$$<\/jats:tex-math>\n \n poly<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time algorithms for three general classes of MOT cost structures: (1) graphical structure; (2) set-optimization structure; and (3) low-rank plus sparse structure. For structure (1), we recover the known result that Sinkhorn has $$\\mathrm {poly}(n,k)$$<\/jats:tex-math>\n \n poly<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> runtime; moreover, we provide the first $$\\mathrm {poly}(n,k)$$<\/jats:tex-math>\n \n poly<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time algorithms for computing solutions that are exact and sparse. For structures (2)-(3), we give the first $$\\mathrm {poly}(n,k)$$<\/jats:tex-math>\n \n poly<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n ,<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time algorithms, even for approximate computation. Together, these three structures encompass many\u2014if not most\u2014current applications of MOT.<\/jats:p>","DOI":"10.1007\/s10107-022-01868-7","type":"journal-article","created":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T15:05:04Z","timestamp":1660662304000},"page":"1107-1178","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Polynomial-time algorithms for multimarginal optimal transport problems with structure"],"prefix":"10.1007","volume":"199","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7367-0097","authenticated-orcid":false,"given":"Jason M.","family":"Altschuler","sequence":"first","affiliation":[]},{"given":"Enric","family":"Boix-Adser\u00e0","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,16]]},"reference":[{"issue":"1","key":"1868_CR1","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1287\/opre.1110.1011","volume":"60","author":"S Agrawal","year":"2012","unstructured":"Agrawal, S., Ding, Y., Saberi, A., Ye, Y.: Price of correlations in stochastic optimization. Oper. Res. 60(1), 150\u2013162 (2012)","journal-title":"Oper. Res."},{"issue":"2","key":"1868_CR2","doi-asserted-by":"crossref","first-page":"904","DOI":"10.1137\/100805741","volume":"43","author":"M Agueh","year":"2011","unstructured":"Agueh, M., Carlier, G.: Barycenters in the Wasserstein space. SIAM J. on Math. Anal. 43(2), 904\u2013924 (2011)","journal-title":"SIAM J. on Math. Anal."},{"key":"1868_CR3","unstructured":"Akagi, Y., Tanaka, Y., Iwata, T., Kurashima, T., Toda, H.: Probabilistic optimal transport based on collective graphical models. (2020). Preprint at arXiv:2006.08866"},{"key":"1868_CR4","first-page":"4429","volume":"32","author":"J Altschuler","year":"2019","unstructured":"Altschuler, J., Bach, F., Rudi, A., Niles-Weed, J.: Massively scalable Sinkhorn distances via the Nystr\u00f6m method. Adv. in Neural Inf. Process. Syst. 32, 4429\u20134439 (2019)","journal-title":"Adv. in Neural Inf. Process. Syst."},{"key":"1868_CR5","unstructured":"Altschuler, J., Weed, J., Rigollet, P.: Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. Advances in Neural Information Processing Systems (2017)"},{"key":"1868_CR6","doi-asserted-by":"crossref","DOI":"10.1016\/j.disopt.2021.100669","volume":"42","author":"JM Altschuler","year":"2021","unstructured":"Altschuler, J.M., Boix-Adser\u00e0, E.: Hardness results for Multimarginal Optimal Transport problems. Discrete Optim. 42, 100669 (2021)","journal-title":"Discrete Optim."},{"key":"1868_CR7","first-page":"44","volume":"22","author":"JM Altschuler","year":"2021","unstructured":"Altschuler, J.M., Boix-Adser\u00e0, E.: Wasserstein barycenters can be computed in polynomial time in fixed dimension. J. of Machine Learning Res. 22, 44\u20131 (2021)","journal-title":"J. of Machine Learning Res."},{"key":"1868_CR8","doi-asserted-by":"crossref","unstructured":"Altschuler, J.M., Boix-Adser\u00e0, E.: Wasserstein barycenters are NP-hard to compute. SIAM Journal on Mathematics of Data Science (2022)","DOI":"10.1137\/21M1390062"},{"key":"1868_CR9","doi-asserted-by":"crossref","unstructured":"Altschuler, J.M., Parrilo, P.A.: Near-linear convergence of the Random Osborne algorithm for Matrix Balancing. Mathematical Programming, 1\u201335 (2022)","DOI":"10.1007\/s10107-022-01825-4"},{"issue":"2","key":"1868_CR10","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/s00186-016-0549-x","volume":"84","author":"E Anderes","year":"2016","unstructured":"Anderes, E., Borgwardt, S., Miller, J.: Discrete Wasserstein barycenters: Optimal transport for discrete data. Math. Methods of Oper. Res. 84(2), 389\u2013409 (2016)","journal-title":"Math. Methods of Oper. Res."},{"issue":"2\u20133","key":"1868_CR11","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1561\/2200000039","volume":"6","author":"F Bach","year":"2013","unstructured":"Bach, F.: Learning with submodular functions: A convex optimization perspective. Found. and Trends in Mach. Learning 6(2\u20133), 145\u2013373 (2013)","journal-title":"Found. and Trends in Mach. Learning"},{"issue":"3","key":"1868_CR12","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1109\/TR.1986.4335422","volume":"35","author":"MO Ball","year":"1986","unstructured":"Ball, M.O.: Computational complexity of network reliability analysis: An overview. IEEE Trans. on Reliab. 35(3), 230\u2013239 (1986)","journal-title":"IEEE Trans. on Reliab."},{"key":"1868_CR13","first-page":"673","volume":"7","author":"MO Ball","year":"1995","unstructured":"Ball, M.O., Colbourn, C.J., Provan, J.S.: Network reliability. Handbooks in Oper. Res. and Management Sci. 7, 673\u2013762 (1995)","journal-title":"Handbooks in Oper. Res. and Management Sci."},{"issue":"2","key":"1868_CR14","doi-asserted-by":"crossref","first-page":"A1111","DOI":"10.1137\/141000439","volume":"37","author":"J-D Benamou","year":"2015","unstructured":"Benamou, J.-D., Carlier, G., Cuturi, M., Nenna, L., Peyr\u00e9, G.: Iterative Bregman projections for regularized transportation problems. SIAM J. on Scientific Comput. 37(2), A1111\u2013A1138 (2015)","journal-title":"SIAM J. on Scientific Comput."},{"issue":"08","key":"1868_CR15","doi-asserted-by":"crossref","first-page":"1553","DOI":"10.1142\/S0218202519500283","volume":"29","author":"J-D Benamou","year":"2019","unstructured":"Benamou, J.-D., Carlier, G., Di Marino, S., Nenna, L.: An entropy minimization approach to second-order variational mean-field games. Math. Models and Methods in Appl. Sci. 29(08), 1553\u20131583 (2019)","journal-title":"Math. Models and Methods in Appl. Sci."},{"key":"1868_CR16","doi-asserted-by":"crossref","unstructured":"Benamou, J.-D., Carlier, G., Nenna, L.: A numerical method to solve multi-marginal optimal transport problems with Coulomb cost. In: Splitting Methods in Communication, Imaging, Science, and Engineering, pp. 577\u2013601. Springer (2016)","DOI":"10.1007\/978-3-319-41589-5_17"},{"issue":"1","key":"1868_CR17","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s00211-018-0995-x","volume":"142","author":"J-D Benamou","year":"2019","unstructured":"Benamou, J.-D., Carlier, G., Nenna, L.: Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm. Numerische Mathematik 142(1), 33\u201354 (2019)","journal-title":"Numerische Mathematik"},{"key":"1868_CR18","volume-title":"Introduction to linear optimization","author":"D Bertsimas","year":"1997","unstructured":"Bertsimas, D., Tsitsiklis, J.N.: Introduction to linear optimization, vol. 6. Athena Scientific Belmont, MA (1997)"},{"key":"1868_CR19","unstructured":"Blanchet, J., Jambulapati, A., Kent, C., Sidford, A.: Towards optimal running times for optimal transport. (2018). Preprint at arXiv:1810.07717"},{"key":"1868_CR20","unstructured":"Blondel, M., Seguy, V., Rolet, A.: Smooth and sparse optimal transport. In: International conference on Artificial Intelligence and Statistics, pp. 880\u2013889. PMLR (2018)"},{"issue":"6","key":"1868_CR21","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. on comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. on comput."},{"key":"1868_CR22","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Treewidth: Structure and algorithms. In: International Colloquium on Structural Information and Communication Complexity, pp. 11\u201325. Springer (2007)","DOI":"10.1007\/978-3-540-72951-8_3"},{"issue":"2","key":"1868_CR23","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1090\/S0894-0347-1989-0969419-8","volume":"2","author":"Y Brenier","year":"1989","unstructured":"Brenier, Y.: The least action principle and the related concept of generalized flows for incompressible perfect fluids. J. of the Am. Math. Soc. 2(2), 225\u2013255 (1989)","journal-title":"J. of the Am. Math. Soc."},{"issue":"4","key":"1868_CR24","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1007\/BF00375139","volume":"122","author":"Y Brenier","year":"1993","unstructured":"Brenier, Y.: The dual least action problem for an ideal, incompressible fluid. Archive for Rational Mech. and Anal. 122(4), 323\u2013351 (1993)","journal-title":"Archive for Rational Mech. and Anal."},{"issue":"4","key":"1868_CR25","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1002\/(SICI)1097-0312(199904)52:4<411::AID-CPA1>3.0.CO;2-3","volume":"52","author":"Y Brenier","year":"1999","unstructured":"Brenier, Y.: Minimal geodesics on groups of volume-preserving maps and generalized solutions of the Euler equations. Commun. on Pure and Appl. Math. 52(4), 411\u2013452 (1999)","journal-title":"Commun. on Pure and Appl. Math."},{"issue":"14\u201317","key":"1868_CR26","doi-asserted-by":"crossref","first-page":"1982","DOI":"10.1016\/j.physd.2008.02.026","volume":"237","author":"Y Brenier","year":"2008","unstructured":"Brenier, Y.: Generalized solutions and hydrostatic approximation of the Euler equations. Physica D: Nonlinear Phenomena 237(14\u201317), 1982\u20131988 (2008)","journal-title":"Physica D: Nonlinear Phenomena"},{"issue":"6","key":"1868_CR27","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevA.85.062502","volume":"85","author":"G Buttazzo","year":"2012","unstructured":"Buttazzo, G., De Pascale, L., Gori-Giorgi, P.: Optimal-transport formulation of electronic density-functional theory. Phys. Review A 85(6), 062502 (2012)","journal-title":"Phys. Review A"},{"issue":"2","key":"1868_CR28","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/s00199-008-0415-z","volume":"42","author":"G Carlier","year":"2010","unstructured":"Carlier, G., Ekeland, I.: Matching for teams. Econ. Theory 42(2), 397\u2013418 (2010)","journal-title":"Econ. Theory"},{"issue":"6","key":"1868_CR29","doi-asserted-by":"crossref","first-page":"1621","DOI":"10.1051\/m2an\/2015033","volume":"49","author":"G Carlier","year":"2015","unstructured":"Carlier, G., Oberman, A., Oudet, E.: Numerical methods for matching for teams and Wasserstein barycenters. ESAIM: Math. Modelling and Numerical Anal. 49(6), 1621\u20131642 (2015)","journal-title":"ESAIM: Math. Modelling and Numerical Anal."},{"key":"1868_CR30","doi-asserted-by":"crossref","unstructured":"Chen, L., Ma, W., Natarajan, K., Simchi-Levi, D., Yan, Z.: Distributionally robust linear and discrete optimization with marginals. Operations Research (2022)","DOI":"10.1287\/opre.2021.2243"},{"issue":"2","key":"1868_CR31","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s00199-009-0455-z","volume":"42","author":"P-A Chiappori","year":"2010","unstructured":"Chiappori, P.-A., McCann, R.J., Nesheim, L.P.: Hedonic price equilibria, stable matching, and optimal transport: equivalence, topology, and uniqueness. Econ. Theory 42(2), 317\u2013354 (2010)","journal-title":"Econ. Theory"},{"issue":"4","key":"1868_CR32","doi-asserted-by":"crossref","first-page":"548","DOI":"10.1002\/cpa.21437","volume":"66","author":"C Cotar","year":"2013","unstructured":"Cotar, C., Friesecke, G., Kl\u00fcppelberg, C.: Density functional theory and optimal transportation with Coulomb cost. Commun. on Pure and Appl. Math. 66(4), 548\u2013599 (2013)","journal-title":"Commun. on Pure and Appl. Math."},{"key":"1868_CR33","doi-asserted-by":"crossref","unstructured":"Courty, N., Flamary, R., Tuia, D., Rakotomamonjy, A.: Optimal transport for domain adaptation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1, (2016)","DOI":"10.1109\/TPAMI.2016.2615921"},{"key":"1868_CR34","unstructured":"Cover, T.M., Thomas, J.A.: Elements of information theory. John Wiley & Sons , Hoboken, New Jersey, US (2012)"},{"key":"1868_CR35","unstructured":"Cuturi, M.: Sinkhorn distances: Lightspeed computation of optimal transport. Advances in Neural Information Processing Systems (2013)"},{"key":"1868_CR36","unstructured":"Cuturi, M., Doucet, A.: Fast computation of Wasserstein barycenters. International Conference on Machine Learning (2014)"},{"key":"1868_CR37","doi-asserted-by":"crossref","unstructured":"Dyer, M., Goldberg, L.A., Greenhill, C., Jerrum, M.: On the relative complexity of approximate counting problems. In: International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 108\u2013119. Springer (2000)","DOI":"10.1007\/3-540-44436-X_12"},{"key":"1868_CR38","doi-asserted-by":"crossref","first-page":"107474","DOI":"10.1016\/j.sigpro.2020.107474","volume":"171","author":"F Elvander","year":"2020","unstructured":"Elvander, F., Haasler, I., Jakobsson, A., Karlsson, J.: Multi-marginal optimal transport using partial information with applications in robust localization and sensor fusion. Signal Process. 171, 107474 (2020)","journal-title":"Signal Process."},{"issue":"5","key":"1868_CR39","doi-asserted-by":"crossref","first-page":"1536","DOI":"10.1137\/060670705","volume":"37","author":"J Feldman","year":"2008","unstructured":"Feldman, J., O\u2019Donnell, R., Servedio, R.A.: Learning mixtures of product distributions over discrete domains. SIAM J. on Comput. 37(5), 1536\u20131564 (2008)","journal-title":"SIAM J. on Comput."},{"key":"1868_CR40","unstructured":"Friedland, S.: Optimal transport, distance between sets of measures and tensor scaling. (2020). Preprint at arXiv:2005.00945"},{"key":"1868_CR41","doi-asserted-by":"crossref","unstructured":"Gertsbakh, I., Shpungin, Y.: Network reliability and resilience. Springer Science & Business Media, Heidelberg, Germany (2011)","DOI":"10.1007\/978-3-642-22374-7"},{"issue":"1","key":"1868_CR42","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1017\/S096354830600767X","volume":"16","author":"LA Goldberg","year":"2007","unstructured":"Goldberg, L.A., Jerrum, M.: The complexity of ferromagnetic Ising with local fields. Comb., Probab. and Comput. 16(1), 43\u201361 (2007)","journal-title":"Comb., Probab. and Comput."},{"issue":"2","key":"1868_CR43","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"1868_CR44","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric algorithms and combinatorial optimization, vol. 2. Springer Science & Business Media, Heidelberg, Germany (2012)"},{"issue":"3","key":"1868_CR45","doi-asserted-by":"crossref","first-page":"964","DOI":"10.1137\/18M1201846","volume":"48","author":"H Guo","year":"2019","unstructured":"Guo, H., Jerrum, M.: A polynomial-time approximation algorithm for all-terminal network reliability. SIAM J. on Comput. 48(3), 964\u2013978 (2019)","journal-title":"SIAM J. on Comput."},{"key":"1868_CR46","doi-asserted-by":"crossref","unstructured":"Haasler, I., Ringh, A., Chen, Y., Karlsson, J.: Estimating ensemble flows on a hidden Markov chain. In: IEEE Conference on Decision and Control, pp. 1331\u20131338. IEEE (2019)","DOI":"10.1109\/CDC40024.2019.9029787"},{"key":"1868_CR47","unstructured":"Haasler, I., Ringh, A., Chen, Y., Karlsson, J.: Multi-marginal optimal transport and Schr\u00f6dinger bridges on trees. (2020). Preprint at arXiv:2004.06909"},{"key":"1868_CR48","unstructured":"Haasler, I., Ringh, A., Chen, Y., Karlsson, J.: Scalable computation of dynamic flow problems via multi-marginal graph-structured optimal transport. (2021). Preprint at arXiv:2106.14485"},{"key":"1868_CR49","doi-asserted-by":"crossref","unstructured":"Haasler, I., Singh, R., Zhang, Q., Karlsson, J., Chen, Y.: Multi-marginal optimal transport and probabilistic graphical models. IEEE Transactions on Information Theory (2021)","DOI":"10.1109\/TIT.2021.3077465"},{"key":"1868_CR50","doi-asserted-by":"crossref","unstructured":"Haneveld, W.K.: Robustness against dependence in PERT: An application of duality and distributions with known marginals. In: Stochastic Programming, pp. 153\u2013182. Springer (1986)","DOI":"10.1007\/BFb0121119"},{"key":"1868_CR51","unstructured":"Jaggi, M.: Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In: International Conference on Machine Learning, pp. 427\u2013435 (2013)"},{"issue":"3","key":"1868_CR52","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1137\/S0036144501387141","volume":"43","author":"DR Karger","year":"2001","unstructured":"Karger, D.R.: A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM Rev. 43(3), 499\u2013522 (2001)","journal-title":"SIAM Rev."},{"issue":"1","key":"1868_CR53","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"LG Khachiyan","year":"1980","unstructured":"Khachiyan, L.G.: Polynomial algorithms in linear programming. USSR Comput. Math. and Math. Phys. 20(1), 53\u201372 (1980)","journal-title":"USSR Comput. Math. and Math. Phys."},{"issue":"3","key":"1868_CR54","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1137\/07070111X","volume":"51","author":"TG Kolda","year":"2009","unstructured":"Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51(3), 455\u2013500 (2009)","journal-title":"SIAM Rev."},{"key":"1868_CR55","unstructured":"Koller, D., Friedman, N.: Probabilistic graphical models: principles and techniques. MIT Press, Cambridge, Massachusetts, US (2009)"},{"issue":"1","key":"1868_CR56","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal","year":"1956","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. of the Am. Math. soc. 7(1), 48\u201350 (1956)","journal-title":"Proc. of the Am. Math. soc."},{"key":"1868_CR57","unstructured":"L\u00e9onard, C.: A survey of the Schr\u0308odinger problem and some of its connections with optimal transport (2013). Preprint at arXiv:1308.0215"},{"key":"1868_CR58","unstructured":"Lin, T., Ho, N., Cuturi, M., Jordan, M.I.: On the complexity of approximating multimarginal optimal transport (2019). Preprint at arXiv:1910.00152"},{"key":"1868_CR59","doi-asserted-by":"crossref","unstructured":"Linial, N., Samorodnitsky, A., Wigderson, A.: A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents. In: Symposium on Theory of Computing, pp. 644\u2013652 (1998)","DOI":"10.1145\/276698.276880"},{"issue":"4","key":"1868_CR60","doi-asserted-by":"crossref","first-page":"803","DOI":"10.1137\/1126086","volume":"26","author":"G Makarov","year":"1982","unstructured":"Makarov, G.: Estimates for the distribution function of a sum of two random variables when the marginal distributions are fixed. Theory of Probab. and its Appl. 26(4), 803\u2013806 (1982)","journal-title":"Theory of Probab. and its Appl."},{"issue":"3","key":"1868_CR61","doi-asserted-by":"crossref","first-page":"671","DOI":"10.2307\/3213097","volume":"16","author":"I Meilijson","year":"1979","unstructured":"Meilijson, I., N\u00e1das, A.: Convex majorization with an application to the length of critical paths. J. of Appl. Probab. 16(3), 671\u2013677 (1979)","journal-title":"J. of Appl. Probab."},{"issue":"6","key":"1868_CR62","doi-asserted-by":"crossref","first-page":"1511","DOI":"10.1287\/mnsc.2014.1906","volume":"60","author":"VK Mishra","year":"2014","unstructured":"Mishra, V.K., Natarajan, K., Padmanabhan, D., Teo, C.-P., Li, X.: On theoretical and empirical aspects of marginal distribution choice models. Management Sci. 60(6), 1511\u20131531 (2014)","journal-title":"Management Sci."},{"issue":"3","key":"1868_CR63","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0016-0032(56)90559-2","volume":"262","author":"EF Moore","year":"1956","unstructured":"Moore, E.F., Shannon, C.E.: Reliable circuits using less reliable relays. J. of the Franklin Institute 262(3), 191\u2013208 (1956)","journal-title":"J. of the Franklin Institute"},{"key":"1868_CR64","doi-asserted-by":"crossref","unstructured":"Muzellec, B., Nock, R., Patrini, G., Nielsen, F.: Tsallis regularized optimal transport and ecological inference. In: AAAI Conference on Artificial Intelligence, volume\u00a031 (2017)","DOI":"10.1609\/aaai.v31i1.10854"},{"issue":"3","key":"1868_CR65","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1147\/rd.233.0339","volume":"23","author":"A Nadas","year":"1979","unstructured":"Nadas, A.: Probabilistic PERT. IBM J. of Res. and Dev. 23(3), 339\u2013347 (1979)","journal-title":"IBM J. of Res. and Dev."},{"issue":"3","key":"1868_CR66","doi-asserted-by":"crossref","first-page":"453","DOI":"10.1287\/mnsc.1080.0951","volume":"55","author":"K Natarajan","year":"2009","unstructured":"Natarajan, K., Song, M., Teo, C.-P.: Persistency model and its applications in choice modeling. Management Sci. 55(3), 453\u2013469 (2009)","journal-title":"Management Sci."},{"key":"1868_CR67","unstructured":"Nenna, L.: Numerical methods for multi-marginal optimal transportation. PhD thesis (2016)"},{"key":"1868_CR68","doi-asserted-by":"crossref","unstructured":"Padmanabhan, D., Ahipasaoglu, S.D., Ramachandra, A., Natarajan, K.: Extremal probability bounds in combinatorial optimization (2021). Preprint at arXiv:2109.01591","DOI":"10.2139\/ssrn.3912018"},{"issue":"3","key":"1868_CR69","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1379759.1379762","volume":"55","author":"CH Papadimitriou","year":"2008","unstructured":"Papadimitriou, C.H., Roughgarden, T.: Computing correlated equilibria in multi-player games. J. of the ACM 55(3), 1\u201329 (2008)","journal-title":"J. of the ACM"},{"key":"1868_CR70","unstructured":"Peyr\u00e9, G., Cuturi, M.: Computational optimal transport. Foundations and Trends in Machine Learning (2017)"},{"issue":"1\u20132","key":"1868_CR71","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/j.cviu.2006.11.011","volume":"107","author":"F Piti\u00e9","year":"2007","unstructured":"Piti\u00e9, F., Kokaram, A.C., Dahyot, R.: Automated colour grading using colour distribution transfer. Comput. Vision and Image Underst. 107(1\u20132), 123\u2013137 (2007)","journal-title":"Comput. Vision and Image Underst."},{"issue":"4","key":"1868_CR72","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1137\/0212053","volume":"12","author":"JS Provan","year":"1983","unstructured":"Provan, J.S., Ball, M.O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. on Comput. 12(4), 777\u2013788 (1983)","journal-title":"SIAM J. on Comput."},{"key":"1868_CR73","unstructured":"Quanrud, K.: Approximating optimal transport with linear programs. In: Symposium on Simplicity in Algorithms (2018)"},{"key":"1868_CR74","doi-asserted-by":"crossref","unstructured":"Rabin, J., Peyr\u00e9, G., Delon, J., Bernot, M.: Wasserstein barycenter and its application to texture mixing. In: International Conference on Scale Space and Variational Methods in Computer Vision, pp. 435\u2013446. Springer (2011)","DOI":"10.1007\/978-3-642-24785-9_37"},{"key":"1868_CR75","doi-asserted-by":"crossref","unstructured":"R\u00fcschendorf, L.: Random variables with maximum sums. Advances in Applied Probability, pp. 623\u2013632 (1982)","DOI":"10.2307\/1426677"},{"issue":"2","key":"1868_CR76","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1006\/jmva.2001.2005","volume":"81","author":"L R\u00fcschendorf","year":"2002","unstructured":"R\u00fcschendorf, L., Uckelmann, L.: On the n-coupling problem. J. of Multivar. Anal. 81(2), 242\u2013258 (2002)","journal-title":"J. of Multivar. Anal."},{"key":"1868_CR77","doi-asserted-by":"crossref","unstructured":"Singh, R., Haasler, I., Zhang, Q., Karlsson, J., Chen, Y.: Incremental inference of collective graphical models. IEEE Control Systems Letters (2020)","DOI":"10.1109\/LCSYS.2020.3002731"},{"issue":"4","key":"1868_CR78","doi-asserted-by":"crossref","first-page":"402","DOI":"10.2307\/2314570","volume":"74","author":"R Sinkhorn","year":"1967","unstructured":"Sinkhorn, R.: Diagonal equivalence to matrices with prescribed row and column sums. The Am. Math. Monthly 74(4), 402\u2013405 (1967)","journal-title":"The Am. Math. Monthly"},{"issue":"4","key":"1868_CR79","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2766963","volume":"34","author":"J Solomon","year":"2015","unstructured":"Solomon, J., De Goes, F., Peyr\u00e9, G., Cuturi, M., Butscher, A., Nguyen, A., Du, T., Guibas, L.: Convolutional Wasserstein distances: Efficient optimal transportation on geometric domains. ACM Trans. on Graphics 34(4), 1\u201311 (2015)","journal-title":"ACM Trans. on Graphics"},{"issue":"1","key":"1868_CR80","first-page":"312","volume":"19","author":"S Srivastava","year":"2018","unstructured":"Srivastava, S., Li, C., Dunson, D.B.: Scalable Bayes via barycenter in Wasserstein space. J. of Mach. Learning Res. 19(1), 312\u2013346 (2018)","journal-title":"J. of Mach. Learning Res."},{"issue":"4","key":"1868_CR81","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1145\/263867.263872","volume":"44","author":"M Stoer","year":"1997","unstructured":"Stoer, M., Wagner, F.: A simple min-cut algorithm. J. of the ACM 44(4), 585\u2013591 (1997)","journal-title":"J. of the ACM"},{"key":"1868_CR82","unstructured":"Teh, Y.W., Welling, M.: The unified propagation and scaling algorithm. Advances in Neural Information Processing Systems, 953\u2013960 (2002)"},{"key":"1868_CR83","doi-asserted-by":"crossref","unstructured":"Trefethen, L.N.: Approximation theory and approximation practice, volume 164. SIAM (2019)","DOI":"10.1137\/1.9781611975949"},{"key":"1868_CR84","doi-asserted-by":"crossref","unstructured":"Tupitsa, N., Dvurechensky, P., Gasnikov, A., Uribe, C.A.: Multimarginal optimal transport by accelerated alternating minimization. In: 2020 IEEE Conference on Decision and Control, pp. 6132\u20136137. IEEE (2020)","DOI":"10.1109\/CDC42340.2020.9304010"},{"issue":"3","key":"1868_CR85","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. on Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. on Comput."},{"key":"1868_CR86","unstructured":"Villani, C.: Topics in optimal transportation. Number 58. American Mathematical Society, Providence, Rhode Island, US (2003)"},{"key":"1868_CR87","first-page":"961","volume":"41","author":"MJ Wainwright","year":"2003","unstructured":"Wainwright, M.J., Jordan, M.I.: Variational inference in graphical models: The view from the marginal polytope. In Allerton Conf. on Commun., Control, and Comput. 41, 961\u2013971 (2003)","journal-title":"In Allerton Conf. on Commun., Control, and Comput."},{"key":"1868_CR88","doi-asserted-by":"crossref","unstructured":"Wainwright, M.J., Jordan, M.I.: Graphical models, exponential families, and variational inference. Now Publishers Inc, Hanover, Massachusetts, US (2008)","DOI":"10.1561\/9781601981851"},{"issue":"4","key":"1868_CR89","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1287\/opre.34.4.595","volume":"34","author":"G Weiss","year":"1986","unstructured":"Weiss, G.: Stochastic bounds on distributions of optimal value functions with applications to PERT, network flows and reliability. Oper. Res. 34(4), 595\u2013605 (1986)","journal-title":"Oper. Res."},{"key":"1868_CR90","unstructured":"Wilson, A.G.: The use of entropy maximising models, in the theory of trip distribution, mode split and route split. Journal of Transport Economics and Policy, 108\u2013126 (1969)"},{"key":"1868_CR91","doi-asserted-by":"crossref","unstructured":"Young, N.E.: Sequential and parallel algorithms for mixed packing and covering. In: Symposium on Foundations of Computer Science, pp. 538\u2013546. IEEE (2001)","DOI":"10.1109\/SFCS.2001.959930"},{"issue":"2","key":"1868_CR92","first-page":"22","volume":"13","author":"DB Yudin","year":"1976","unstructured":"Yudin, D.B., Nemirovskii, A.S.: Informational complexity and efficient methods for the solution of convex extremal problems. Matekon 13(2), 22\u201345 (1976)","journal-title":"Matekon"},{"issue":"4","key":"1868_CR93","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1002\/net.3230120408","volume":"12","author":"E Zemel","year":"1982","unstructured":"Zemel, E.: Polynomial algorithms for estimating network reliability. Netw. 12(4), 439\u2013452 (1982)","journal-title":"Netw."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01868-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01868-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01868-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,21]],"date-time":"2023-04-21T17:40:36Z","timestamp":1682098836000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01868-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,16]]},"references-count":93,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2023,5]]}},"alternative-id":["1868"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01868-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2022,8,16]]},"assertion":[{"value":"13 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}