{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T20:51:10Z","timestamp":1768337470007,"version":"3.49.0"},"reference-count":52,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T00:00:00Z","timestamp":1596412800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T00:00:00Z","timestamp":1596412800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["524210"],"award-info":[{"award-number":["524210"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper Res Int J"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s12351-020-00589-z","type":"journal-article","created":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T10:05:22Z","timestamp":1596449122000},"page":"1511-1551","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["An LP-based, strongly-polynomial 2-approximation algorithm for sparse Wasserstein barycenters"],"prefix":"10.1007","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8069-5046","authenticated-orcid":false,"given":"Steffen","family":"Borgwardt","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,8,3]]},"reference":[{"issue":"2","key":"589_CR1","doi-asserted-by":"crossref","first-page":"904","DOI":"10.1137\/100805741","volume":"43","author":"M Agueh","year":"2011","unstructured":"Agueh M, Carlier G (2011) Barycenters in the Wasserstein space. SIAM J Math Anal 43(2):904\u2013924","journal-title":"SIAM J Math Anal"},{"issue":"2","key":"589_CR2","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 (2016) Discrete Wasserstein barycenters: optimal transport for discrete data. Math Methods Oper Res 84(2):389\u2013409","journal-title":"Math Methods Oper Res"},{"issue":"5","key":"589_CR3","doi-asserted-by":"crossref","first-page":"19:1","DOI":"10.1145\/2027216.2027217","volume":"58","author":"D Arthur","year":"2011","unstructured":"Arthur D, Manthey B, R\u00f6glin H (2011) Smoothed analysis of the k-means method. J ACM 58(5):19:1\u201319:31","journal-title":"J ACM"},{"key":"589_CR4","doi-asserted-by":"crossref","unstructured":"Auricchio G, Bassetti F, Gualandi S, Veneroni S (2019) Computing Wasserstein barycenters via linear programming. In: Integration of constraint programming, artificial intelligence, and operations research, pp 355\u2013363","DOI":"10.1007\/978-3-030-19212-9_23"},{"issue":"3","key":"589_CR5","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/s00780-013-0205-8","volume":"17","author":"M Beiglb\u00f6ck","year":"2013","unstructured":"Beiglb\u00f6ck M, Henry-Labordere P, Penkner F (2013) Model-independent bounds for option prices\u2014a mass transport approach. Finance Stoch 17(3):477\u2013501","journal-title":"Finance Stoch"},{"issue":"2","key":"589_CR6","doi-asserted-by":"crossref","first-page":"A1111","DOI":"10.1137\/141000439","volume":"37","author":"JD Benamou","year":"2015","unstructured":"Benamou JD, Carlier G, Cuturi M, Nenna L, Peyr\u00e9 G (2015) Iterative Bregman projections for regularized transportation problems. SIAM J Sci Comput 37(2):A1111\u2013A1138","journal-title":"SIAM J Sci Comput"},{"issue":"11","key":"589_CR7","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1137\/141000671","volume":"59","author":"J Bezanson","year":"2017","unstructured":"Bezanson J, Edelman A, Karpinski S, Shah VB (2017) Julia: a fresh approach to numerical computing. SIAM Rev 59(11):65\u201398","journal-title":"SIAM Rev"},{"key":"589_CR8","doi-asserted-by":"crossref","unstructured":"Bigot J, Klein T (2017) Characterization of barycenters in the Wasserstein space by averaging optimal transport maps. ESAIM: Probability and Statistics 22:35\u201357","DOI":"10.1051\/ps\/2017020"},{"issue":"2","key":"589_CR9","doi-asserted-by":"crossref","first-page":"740","DOI":"10.3150\/13-BEJ585","volume":"21","author":"E Boissard","year":"2015","unstructured":"Boissard E, Gouic TL, Loubes JM (2015) Distribution\u2019s template estimate with Wasserstein metrics. Bernoulli 21(2):740\u2013759","journal-title":"Bernoulli"},{"issue":"1","key":"589_CR10","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1007\/s10851-014-0506-3","volume":"51","author":"N Bonneel","year":"2015","unstructured":"Bonneel N, Rabin J, Peyr\u00e9 G, Pfister H (2015) Sliced and Radon Wasserstein barycenters of measures. J Math Imaging Vis 51(1):22\u201345","journal-title":"J Math Imaging Vis"},{"issue":"1","key":"589_CR11","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1287\/ijoo.2019.0020","volume":"2","author":"S Borgwardt","year":"2020","unstructured":"Borgwardt S, Patterson S (2020) Improved linear programs for discrete barycenters. INFORMS J Optim 2(1):14\u201333","journal-title":"INFORMS J Optim"},{"key":"589_CR12","doi-asserted-by":"crossref","first-page":"062502","DOI":"10.1103\/PhysRevA.85.062502","volume":"85","author":"G Buttazzo","year":"2012","unstructured":"Buttazzo G, Pascale LD, Gori-Giorgi P (2012) Optimal-transport formulation of electronic density-functional theory. Phys Rev A 85:062502","journal-title":"Phys Rev A"},{"issue":"2","key":"589_CR13","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 (2010) Matching for teams. Econ Theory 42(2):397\u2013418","journal-title":"Econ Theory"},{"issue":"6","key":"589_CR14","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 (2015) Numerical methods for matching for teams and Wasserstein barycenters. ESAIM Math Model Numer Anal 49(6):1621\u20131642","journal-title":"ESAIM Math Model Numer Anal"},{"issue":"2","key":"589_CR15","doi-asserted-by":"crossref","first-page":"1385","DOI":"10.1137\/15M1050264","volume":"49","author":"G Carlier","year":"2017","unstructured":"Carlier G, Duval V, Peyr\u00e9 G, Schmitzer B (2017) Convergence of entropic schemes for optimal transport and gradient flows. SIAM J Math Anal 49(2):1385\u20131418","journal-title":"SIAM J Math Anal"},{"issue":"2","key":"589_CR16","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s00199-009-0455-z","volume":"42","author":"PA Chiaporri","year":"2010","unstructured":"Chiaporri PA, McCann R, Nesheim L (2010) Hedonic price equilibiria, stable matching and optimal transport; equivalence, topology and uniqueness. Econ Theory 42(2):317\u2013354","journal-title":"Econ Theory"},{"key":"589_CR17","unstructured":"Claici S, Chien E, Solomon J (2018) Stochastic Wasserstein Barycenters. In: Proceedings of the 35th international conference on machine learning (PMLR) 80:999\u20131008"},{"issue":"4","key":"589_CR18","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 (2013) Density functional theory and optimal transportation with Coulomb cost. Commun Pure Appl Math 66(4):548\u2013599","journal-title":"Commun Pure Appl Math"},{"key":"589_CR19","first-page":"2292","volume":"26","author":"M Cuturi","year":"2013","unstructured":"Cuturi M (2013) Sinkhorn distances: lightspeed computation of optimal transport. Adv Neural Inf Process Syst 26:2292\u20132300","journal-title":"Adv Neural Inf Process Syst"},{"key":"589_CR20","unstructured":"Cuturi M, Doucet A (2014) Fast Computation of Wasserstein Barycenters. In: Proceedings of the 31st international conference on machine learning (ICML-14), pp 685\u2013693"},{"issue":"1","key":"589_CR21","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s11222-018-9800-z","volume":"29","author":"E del Barrio","year":"2019","unstructured":"del Barrio E, Cuesta-Albertos J, Matr\u00e1n C, Mayo-\u00cdscar A (2019) Robust clustering tools based on optimal transportation. Stat Comput 29(1):139\u2013160","journal-title":"Stat Comput"},{"key":"589_CR22","doi-asserted-by":"crossref","first-page":"A1961","DOI":"10.1137\/17M1132665","volume":"40","author":"M Essid","year":"2017","unstructured":"Essid M, Solomon J (2017) Quadratically regularized optimal transport on graphs. SIAM J Sci Comput 40:A1961\u2013A1986","journal-title":"SIAM J Sci Comput"},{"key":"589_CR23","unstructured":"Frogner C, Mirzazadeh F, Solomon J (2019) Learning Embeddings into Entropic Wasserstein Spaces. eprint arXiv:190503329"},{"issue":"4","key":"589_CR24","doi-asserted-by":"crossref","first-page":"1085","DOI":"10.1287\/moor.2017.0896","volume":"43","author":"S Gadat","year":"2018","unstructured":"Gadat S, Gavra I, Risser L (2018) How to calculate the barycenter of a weighted graph. Math Oper Res 43(4):1085\u20131118","journal-title":"Math Oper Res"},{"issue":"1","key":"589_CR25","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1214\/13-AAP925","volume":"24","author":"A Galichon","year":"2014","unstructured":"Galichon A, Henry-Labordere P, Touzi N (2014) A stochastic control approach to non-arbitrage bounds given marginals, with an application to lookback options. Ann Appl Probab 24(1):312\u2013336","journal-title":"Ann Appl Probab"},{"issue":"2","key":"589_CR26","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0165-1684(98)00139-X","volume":"71","author":"A Jain","year":"1998","unstructured":"Jain A, Zhong Y, Dubuisson-Jolly MP (1998) Deformable template models: a review. Signal Process 71(2):109\u2013129","journal-title":"Signal Process"},{"key":"589_CR27","unstructured":"Kroshnin A, Dvinskikh D, Dvurechensky P, Gasnikov A, Tupitsa N, Uribe C (2019) On the Complexity of Approximating Wasserstein Barycenter. In: Proceedings of the 36th international conference on machine learning, proceedings of machine learning research, vol\u00a097, pp 3530\u20133540"},{"issue":"11","key":"589_CR28","doi-asserted-by":"crossref","first-page":"2278","DOI":"10.1109\/5.726791","volume":"86","author":"Y LeCun","year":"1998","unstructured":"LeCun Y, Bottou L, Bengio Y, Haffner P (1998) Gradient-based learning applied to document recognition. Proc IEEE 86(11):2278\u20132324","journal-title":"Proc IEEE"},{"issue":"2","key":"589_CR29","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"SP Lloyd","year":"1982","unstructured":"Lloyd SP (1982) Least squares quantization in PCM. IEEE Trans Inf Theory 28(2):129\u2013137","journal-title":"IEEE Trans Inf Theory"},{"issue":"2","key":"589_CR30","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1287\/ijoc.2014.0623","volume":"27","author":"M Lubin","year":"2015","unstructured":"Lubin M, Dunning I (2015) Computing in operations research using Julia. INFORMS J Comput 27(2):238\u2013248","journal-title":"INFORMS J Comput"},{"key":"589_CR31","first-page":"5859","volume":"31","author":"G Luise","year":"2018","unstructured":"Luise G, Rudi A, Pontil M, Ciliberto C (2018) Differential Properties of Sinkhorn approximation for learning with Wasserstein distance. Adv Neural Inf Process Syst 31:5859\u20135870","journal-title":"Adv Neural Inf Process Syst"},{"key":"589_CR32","unstructured":"Luise G, Salzo S, Pontil M, Ciliberto C (2019) Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm. eprint arXiv:190513194"},{"key":"589_CR33","unstructured":"MacQueen JB (1967) Some methods of classification and analysis of multivariate observations. In: Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, pp 281\u2013297"},{"key":"589_CR34","doi-asserted-by":"crossref","unstructured":"Mileyko Y, Mukherjee S, Harer J (2011) Probability measures on the space of persistence diagrams. Inverse Problems 27(12)","DOI":"10.1088\/0266-5611\/27\/12\/124007"},{"key":"589_CR35","unstructured":"Miller J (2016) Transportation networks and matroids: algorithms through circuits and polyhedrality. PhD thesis, University of California Davis"},{"key":"589_CR36","doi-asserted-by":"crossref","first-page":"1173","DOI":"10.1214\/15-EJS1030","volume":"9","author":"E Munch","year":"2015","unstructured":"Munch E, Turner K, Bendich P, Mukherjee S, Mattingly J, Harer J (2015) Probabilistic Fr\u00e9chet means for time varying persistence diagrams. Electron J Stat 9:1173\u20131204","journal-title":"Electron J Stat"},{"issue":"1","key":"589_CR37","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1146\/annurev-statistics-030718-104938","volume":"6","author":"VM Panaretos","year":"2019","unstructured":"Panaretos VM, Zemel Y (2019) Statistical aspects of Wasserstein distances. Annu Rev Stat Appl 6(1):405\u2013431","journal-title":"Annu Rev Stat Appl"},{"issue":"4","key":"589_CR38","doi-asserted-by":"crossref","first-page":"1623","DOI":"10.3934\/dcds.2014.34.1623","volume":"34","author":"B Pass","year":"2014","unstructured":"Pass B (2014) Multi-marginal optimal transport and multi-agent matching problems: uniqueness and structure of solutions. Discrete Contin Dyn Syst A 34(4):1623\u20131639","journal-title":"Discrete Contin Dyn Syst A"},{"issue":"5\u20136","key":"589_CR39","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1561\/2200000073","volume":"11","author":"G Peyr\u00e9","year":"2019","unstructured":"Peyr\u00e9 G, Cuturi M (2019) Computational optimal transport. Found Trends Mach Learn 11(5\u20136):355\u2013607","journal-title":"Found Trends Mach Learn"},{"key":"589_CR40","first-page":"435","volume":"6667","author":"J Rabin","year":"2012","unstructured":"Rabin J, Peyr\u00e9 G, Delon J, Bernot M (2012) Wasserstein barycenter and its application to texture mixing. Scale Space Var Methods Comput Vis Lect Notes Comput Sci 6667:435\u2013446","journal-title":"Scale Space Var Methods Comput Vis Lect Notes Comput Sci"},{"issue":"4","key":"589_CR41","doi-asserted-by":"crossref","first-page":"67:1","DOI":"10.1145\/2601097.2601175","volume":"33","author":"J Solomon","year":"2014","unstructured":"Solomon J, Rustamov R, Guibas L, Butscher A (2014) Earth mover\u2019s distances on discrete surfaces. ACM Trans Graph 33(4):67:1\u201367:12","journal-title":"ACM Trans Graph"},{"issue":"4","key":"589_CR42","doi-asserted-by":"crossref","first-page":"66: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 (2015) Convolutional Wasserstein distances: efficient optimal transportation on geometric domains. ACM Trans Graph 34(4):66:1\u201366:11","journal-title":"ACM Trans Graph"},{"key":"589_CR43","first-page":"1","volume":"19","author":"S Srivastava","year":"2018","unstructured":"Srivastava S, Li C, Dunson DB (2018) Scalable bayes via barycenter in Wasserstein space. J Mach Learn Res 19:1\u201335","journal-title":"J Mach Learn Res"},{"key":"589_CR44","first-page":"2644","volume":"30","author":"M Staib","year":"2017","unstructured":"Staib M, Claici S, Solomon J, Jegelka S (2017) Parallel streaming Wasserstein barycenters. Adv Neural Inf Process Syst 30:2644\u20132655","journal-title":"Adv Neural Inf Process Syst (NIPS)"},{"issue":"2","key":"589_CR45","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E Tardos","year":"1986","unstructured":"Tardos E (1986) A strongly polynomial algorithm to solve combinatorial linear programs. Oper Res 34(2):250\u2013256","journal-title":"Oper Res"},{"issue":"1","key":"589_CR46","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1137\/S0036141002404838","volume":"37","author":"A Trouv\u00e9","year":"2005","unstructured":"Trouv\u00e9 A, Younes L (2005) Local geometry of deformable templates. SIAM J Math Anal 37(1):17\u201359","journal-title":"SIAM J Math Anal"},{"issue":"1","key":"589_CR47","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/s00454-014-9604-7","volume":"52","author":"K Turner","year":"2014","unstructured":"Turner K, Mileyko Y, Mukherjee S, Harer J (2014) Fr\u00e9chet means for distributions of persistence diagrams. Discrete Comput Geom 52(1):44\u201370","journal-title":"Discrete Comput Geom"},{"key":"589_CR48","volume-title":"Topics in optimal transportation","author":"C Villani","year":"2003","unstructured":"Villani C (2003) Topics in optimal transportation. American Mathematical Society, Providence"},{"key":"589_CR49","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-71050-9","volume-title":"Optimal transport: old and new","author":"C Villani","year":"2009","unstructured":"Villani C (2009) Optimal transport: old and new. Springer, Berlin"},{"key":"589_CR50","unstructured":"Yang L, Li J, Sun D, Toh KC (2019) A Fast Globally Linearly Convergent Algorithm for the Computation of Wasserstein Barycenters. eprint arXiv:180904249"},{"issue":"9","key":"589_CR51","doi-asserted-by":"crossref","first-page":"2317","DOI":"10.1109\/TSP.2017.2659647","volume":"65","author":"J Ye","year":"2017","unstructured":"Ye J, Wu P, Wang JZ, Li J (2017) Fast discrete distribution clustering using Wasserstein barycenter with sparse support. IEEE Trans Signal Process 65(9):2317\u20132332","journal-title":"IEEE Trans Signal Process"},{"issue":"2","key":"589_CR52","doi-asserted-by":"crossref","first-page":"932","DOI":"10.3150\/17-BEJ1009","volume":"25","author":"Y Zemel","year":"2019","unstructured":"Zemel Y, Panaretos V (2019) Fr\u00e9chet means and Procrustes analysis in Wasserstein space. Bernoulli 25(2):932\u2013976","journal-title":"Bernoulli"}],"container-title":["Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12351-020-00589-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12351-020-00589-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12351-020-00589-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T05:08:18Z","timestamp":1647407298000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12351-020-00589-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,3]]},"references-count":52,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["589"],"URL":"https:\/\/doi.org\/10.1007\/s12351-020-00589-z","relation":{},"ISSN":["1109-2858","1866-1505"],"issn-type":[{"value":"1109-2858","type":"print"},{"value":"1866-1505","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,3]]},"assertion":[{"value":"13 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 July 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}