{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:57:37Z","timestamp":1781305057898,"version":"3.54.1"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032286901","type":"print"},{"value":"9783032286918","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-28691-8_33","type":"book-chapter","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:35:40Z","timestamp":1781303740000},"page":"507-520","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Closing the\u00a0Gap: Efficient Algorithms for\u00a0Discrete Wasserstein Barycenters"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-9427-3776","authenticated-orcid":false,"given":"Jiaqi","family":"Wang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5157-1194","authenticated-orcid":false,"given":"Weijun","family":"Xie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,13]]},"reference":[{"issue":"2","key":"33_CR1","doi-asserted-by":"publisher","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. Math. Anal. 43(2), 904\u2013924 (2011)","journal-title":"SIAM J. Math. Anal."},{"key":"33_CR2","unstructured":"Altschuler, J.M., Boix-Adsera, E.: Wasserstein barycenters can be computed in polynomial time in fixed dimension. J. Mach. Learn. Res. 22(44), 1\u201319 (2021). http:\/\/jmlr.org\/papers\/v22\/20-588.html"},{"issue":"1","key":"33_CR3","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1137\/21M1390062","volume":"4","author":"JM Altschuler","year":"2022","unstructured":"Altschuler, J.M., Boix-Adsera, E.: Wasserstein barycenters are NP-hard to compute. SIAM J. Math. Data Sci. 4(1), 179\u2013203 (2022)","journal-title":"SIAM J. Math. Data Sci."},{"issue":"2","key":"33_CR4","doi-asserted-by":"publisher","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 Oper. Res. 84(2), 389\u2013409 (2016)","journal-title":"Math. Methods Oper. Res."},{"issue":"2","key":"33_CR5","doi-asserted-by":"publisher","first-page":"A1111","DOI":"10.1137\/141000439","volume":"37","author":"JD 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. Sci. Comput. 37(2), A1111\u2013A1138 (2015)","journal-title":"SIAM J. Sci. Comput."},{"key":"33_CR6","unstructured":"Bigot, J., Klein, T., et\u00a0al.: Consistent estimation of a population barycenter in the Wasserstein space. ArXiv e-prints 49 (2012)"},{"issue":"4","key":"33_CR7","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1145\/2897824.2925918","volume":"35","author":"N Bonneel","year":"2016","unstructured":"Bonneel, N., Peyr\u00e9, G., Cuturi, M.: Wasserstein barycentric coordinates: histogram regression using optimal transport. ACM Trans. Graph. 35(4), 71\u20131 (2016)","journal-title":"ACM Trans. Graph."},{"issue":"1","key":"33_CR8","doi-asserted-by":"publisher","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.: Sliced and radon Wasserstein barycenters of measures. J. Math. Imaging Vis. 51(1), 22\u201345 (2015)","journal-title":"J. Math. Imaging Vis."},{"issue":"2","key":"33_CR9","doi-asserted-by":"publisher","first-page":"1511","DOI":"10.1007\/s12351-020-00589-z","volume":"22","author":"S Borgwardt","year":"2022","unstructured":"Borgwardt, S.: An LP-based, strongly-polynomial 2-approximation algorithm for sparse Wasserstein barycenters. Oper. Res. Int. Journal 22(2), 1511\u20131551 (2022)","journal-title":"Oper. Res. Int. Journal"},{"issue":"1","key":"33_CR10","first-page":"14","volume":"2","author":"S Borgwardt","year":"2020","unstructured":"Borgwardt, S., Patterson, S.: Improved linear programs for discrete barycenters. Inf. J. Optim. 2(1), 14\u201333 (2020)","journal-title":"Inf. J. Optim."},{"issue":"3","key":"33_CR11","doi-asserted-by":"publisher","first-page":"736","DOI":"10.1007\/s10878-021-00713-5","volume":"41","author":"S Borgwardt","year":"2021","unstructured":"Borgwardt, S., Patterson, S.: On the computational complexity of finding a sparse Wasserstein barycenter. J. Comb. Optim. 41(3), 736\u2013761 (2021)","journal-title":"J. Comb. Optim."},{"key":"33_CR12","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2021.100674","volume":"43","author":"S Borgwardt","year":"2022","unstructured":"Borgwardt, S., Patterson, S.: A column generation approach to the discrete barycenter problem. Discret. Optim. 43, 100674 (2022)","journal-title":"Discret. Optim."},{"key":"33_CR13","doi-asserted-by":"crossref","unstructured":"Carlier, G., Ekeland, I.: Matching for teams. Econ. Theory 42(2), 397\u2013418 (2010). http:\/\/www.jstor.org\/stable\/25619994","DOI":"10.1007\/s00199-008-0415-z"},{"key":"33_CR14","unstructured":"Cheng, K., Aeron, S., Hughes, M.C., Miller, E.L.: Dynamical Wasserstein barycenters for time-series modeling. In: Advances in Neural Information Processing Systems, vol. 34, pp. 27991\u201328003 (2021)"},{"key":"33_CR15","unstructured":"Claici, S., Chien, E., Solomon, J.: Stochastic Wasserstein barycenters. In: International Conference on Machine Learning, pp. 999\u20131008. PMLR (2018)"},{"key":"33_CR16","unstructured":"Cuturi, M., Doucet, A.: Fast computation of Wasserstein barycenters. In: International Conference on Machine Learning, pp. 685\u2013693. PMLR (2014)"},{"key":"33_CR17","unstructured":"Ge, D., Wang, H., Xiong, Z., Ye, Y.: Interior-point methods strike back: solving the Wasserstein barycenter problem. In: Advances in Neural Information Processing Systems, vol. 32 (2019)"},{"key":"33_CR18","unstructured":"Huang, M., Ma, S., Lai, L.: Projection robust Wasserstein barycenters. In: International Conference on Machine Learning, pp. 4456\u20134465. PMLR (2021)"},{"key":"33_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.neuroimage.2020.116847","volume":"220","author":"H Janati","year":"2020","unstructured":"Janati, H., Bazeille, T., Thirion, B., Cuturi, M., Gramfort, A.: Multi-subject MEG\/EEG source imaging with sparse multi-task regression. Neuroimage 220, 116847 (2020)","journal-title":"Neuroimage"},{"key":"33_CR20","unstructured":"Janati, H., Cuturi, M., Gramfort, A.: Debiased Sinkhorn barycenters. In: International Conference on Machine Learning, pp. 4692\u20134701. PMLR (2020)"},{"key":"33_CR21","unstructured":"Kroshnin, A., Tupitsa, N., Dvinskikh, D., Dvurechensky, P., Gasnikov, A., Uribe, C.: On the complexity of approximating Wasserstein barycenters. In: International Conference on Machine Learning, pp. 3530\u20133540. PMLR (2019)"},{"key":"33_CR22","unstructured":"Lau, T.T.K., Liu, H.: Wasserstein distributionally robust optimization with Wasserstein barycenters (2022). arXiv preprint arXiv:2203.12136"},{"key":"33_CR23","unstructured":"Lin, T., Ho, N., Chen, X., Cuturi, M., Jordan, M.: Fixed-support Wasserstein barycenters: computational hardness and fast algorithm. In: Advances in Neural Information Processing Systems, vol. 33, pp. 5368\u20135380 (2020)"},{"key":"33_CR24","doi-asserted-by":"crossref","unstructured":"Lin, Z., Ruszczy\u0144ski, A.: Federated calculation of the free-support transportation barycenter by single-loop dual decomposition (2025). arXiv preprint arXiv:2507.19627","DOI":"10.1007\/s10479-025-07004-w"},{"key":"33_CR25","doi-asserted-by":"crossref","unstructured":"Lindheim, J.V.: Simple approximative algorithms for free-support Wasserstein barycenters. Comput. Optim. Appl. 85(1), 213\u2013246 (2023)","DOI":"10.1007\/s10589-023-00458-3"},{"key":"33_CR26","unstructured":"Luise, G., Salzo, S., Pontil, M., Ciliberto, C.: Sinkhorn barycenters with free support via Frank-Wolfe algorithm. In: Advances in Neural Information Processing Systems, vol. 32 (2019)"},{"issue":"1","key":"33_CR27","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1137\/17M1140431","volume":"11","author":"MA Schmitz","year":"2018","unstructured":"Schmitz, M.A., et al.: Wasserstein dictionary learning: optimal transport-based unsupervised nonlinear dictionary learning. SIAM J. Imag. Sci. 11(1), 643\u2013678 (2018)","journal-title":"SIAM J. Imag. Sci."},{"key":"33_CR28","doi-asserted-by":"crossref","unstructured":"Simon, D., Aberdam, A.: Barycenters of natural images constrained Wasserstein barycenters for image morphing. In: Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition, pp. 7910\u20137919 (2020)","DOI":"10.1109\/CVPR42600.2020.00793"},{"key":"33_CR29","doi-asserted-by":"crossref","unstructured":"Uribe, C.A., Dvinskikh, D., Dvurechensky, P., Gasnikov, A., Nedi\u0107, A.: Distributed computation of Wasserstein barycenters over networks. In: 2018 IEEE Conference on Decision and Control (CDC), pp. 6544\u20136549. IEEE (2018)","DOI":"10.1109\/CDC.2018.8619160"},{"key":"33_CR30","unstructured":"Wang, J., Xie, W.: Closing the gap: efficient algorithms for discrete Wasserstein barycenters (2025). arXiv preprint arXiv:2511.04607"},{"key":"33_CR31","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2021.107945","volume":"116","author":"Y Yan","year":"2021","unstructured":"Yan, Y., et al.: 2D Wasserstein loss for robust facial landmark detection. Pattern Recogn. 116, 107945 (2021)","journal-title":"Pattern Recogn."},{"issue":"21","key":"33_CR32","first-page":"1","volume":"22","author":"L Yang","year":"2021","unstructured":"Yang, L., Li, J., Sun, D., Toh, K.C.: A fast globally linearly convergent algorithm for the computation of Wasserstein barycenters. J. Mach. Learn. Res. 22(21), 1\u201337 (2021)","journal-title":"J. Mach. Learn. Res."},{"issue":"9","key":"33_CR33","doi-asserted-by":"publisher","first-page":"2317","DOI":"10.1109\/TSP.2017.2659647","volume":"65","author":"J Ye","year":"2017","unstructured":"Ye, J., Wu, P., Wang, J.Z., Li, J.: Fast discrete distribution clustering using Wasserstein barycenter with sparse support. IEEE Trans. Signal Process. 65(9), 2317\u20132332 (2017)","journal-title":"IEEE Trans. Signal Process."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-28691-8_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:35:45Z","timestamp":1781303745000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28691-8_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032286901","9783032286918"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28691-8_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"13 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Padua","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.math.unipd.it\/ipco2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}