{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:02:46Z","timestamp":1776783766667,"version":"3.51.2"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T00:00:00Z","timestamp":1613952000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T00:00:00Z","timestamp":1613952000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s10107-021-01627-0","type":"journal-article","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T11:03:58Z","timestamp":1613991838000},"page":"597-640","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Distributionally robust bottleneck combinatorial problems: uncertainty quantification and robust decision making"],"prefix":"10.1007","volume":"196","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5157-1194","authenticated-orcid":false,"given":"Weijun","family":"Xie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shabbir","family":"Ahmed","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"key":"1627_CR1","unstructured":"Abadeh, S.S., Nguyen, V.A., Kuhn, D., Esfahani, P.M.M.: Wasserstein distributionally robust Kalman filtering. In: Advances in Neural Information Processing Systems, pp. 8474\u20138483 (2018)"},{"issue":"3","key":"1627_CR2","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/s10107-005-0638-8","volume":"106","author":"S Ahmed","year":"2006","unstructured":"Ahmed, S.: Convexity and decomposition of mean-risk stochastic programs. Math. Program. 106(3), 433\u2013446 (2006)","journal-title":"Math. Program."},{"issue":"2","key":"1627_CR3","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.orl.2004.04.010","volume":"33","author":"H Albrecher","year":"2005","unstructured":"Albrecher, H.: A note on the asymptotic behaviour of bottleneck problems. Oper. Res. Lett. 33(2), 183\u2013186 (2005)","journal-title":"Oper. Res. Lett."},{"key":"1627_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718829","volume-title":"Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications","author":"A Ben-Tal","year":"2001","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, vol. 2. SIAM, Pathum Wan (2001)"},{"key":"1627_CR5","unstructured":"Bertsimas, D., Shtern, S., Sturt, B.: A data-driven approach for multi-stage linear optimization. Optimization Online"},{"issue":"3","key":"1627_CR6","doi-asserted-by":"publisher","first-page":"830","DOI":"10.1017\/jpr.2019.49","volume":"56","author":"J Blanchet","year":"2019","unstructured":"Blanchet, J., Kang, Y., Murthy, K.: Robust Wasserstein profile inference and applications to machine learning. J. Appl. Prob. 56(3), 830\u2013857 (2019)","journal-title":"J. Appl. Prob."},{"issue":"2","key":"1627_CR7","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1287\/moor.2018.0936","volume":"44","author":"J Blanchet","year":"2019","unstructured":"Blanchet, J., Murthy, K.: Quantifying distributional model risk via optimal transport. Math. Oper. Res. 44(2), 565\u2013600 (2019)","journal-title":"Math. Oper. Res."},{"key":"1627_CR8","unstructured":"Blanchet, J., Murthy, K., Si, N.: Confidence regions in Wasserstein distributionally robust estimation. arXiv preprint arXiv:1906.01614 (2019)"},{"issue":"1","key":"1627_CR9","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/0020-0190(78)90030-3","volume":"7","author":"PM Camerini","year":"1978","unstructured":"Camerini, P.M.: The min-max spanning tree problem and some extensions. Inf. Process. Lett. 7(1), 10\u201314 (1978)","journal-title":"Inf. Process. Lett."},{"key":"1627_CR10","unstructured":"Chen, Z., Kuhn, D., Wiesemann, W.: Data-driven chance constrained programs over Wasserstein balls. arXiv preprint arXiv:1809.00210 (2018)"},{"key":"1627_CR11","doi-asserted-by":"crossref","unstructured":"Chen, Z., Xie, W.: Sharing the value-at-risk under distributional ambiguity. SSRN 3400033 (2019)","DOI":"10.2139\/ssrn.3400033"},{"issue":"3","key":"1627_CR12","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1287\/opre.1090.0741","volume":"58","author":"E Delage","year":"2010","unstructured":"Delage, E., Ye, Y.: Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3), 595\u2013612 (2010)","journal-title":"Oper. Res."},{"key":"1627_CR13","first-page":"68","volume":"20","author":"JC Duchi","year":"2019","unstructured":"Duchi, J.C., Namkoong, H.: Variance-based regularization with convex objectives. J. Mach. Learn. Res. 20, 68\u20131 (2019)","journal-title":"J. Mach. Learn. Res."},{"issue":"3","key":"1627_CR14","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/S0021-9800(70)80083-7","volume":"8","author":"J Edmonds","year":"1970","unstructured":"Edmonds, J., Fulkerson, D.R.: Bottleneck extrema. J. Combin. Theory 8(3), 299\u2013306 (1970)","journal-title":"J. Combin. Theory"},{"issue":"1\u20132","key":"1627_CR15","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s10107-017-1172-1","volume":"171","author":"PM Esfahani","year":"2018","unstructured":"Esfahani, P.M., Kuhn, D.: Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations. Math. Program. 171(1\u20132), 115\u2013166 (2018)","journal-title":"Math. Program."},{"issue":"3\u20134","key":"1627_CR16","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1007\/s00440-014-0583-7","volume":"162","author":"N Fournier","year":"2015","unstructured":"Fournier, N., Guillin, A.: On the rate of convergence in Wasserstein distance of the empirical measure. Probab. Theory Relat. Fields 162(3\u20134), 707\u2013738 (2015)","journal-title":"Probab. Theory Relat. Fields"},{"key":"1627_CR17","unstructured":"Gao, R., Kleywegt, A.J.: Distributionally robust stochastic optimization with wasserstein distance. arXiv preprint arXiv:1604.02199 (2016)"},{"key":"1627_CR18","doi-asserted-by":"crossref","unstructured":"Gao, Y., Chiu, D.-M., Lui, J.: Determining the end-to-end throughput capacity in multi-hop networks: methodology and applications. In: ACM SIGMETRICS Performance Evaluation Review, vol 34, pp 39\u201350. ACM (2006)","DOI":"10.1145\/1140103.1140284"},{"key":"1627_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511841224","volume-title":"Wireless communications","author":"A Goldsmith","year":"2005","unstructured":"Goldsmith, A.: Wireless communications. Cambridge University Press, Cambridge (2005)"},{"issue":"5","key":"1627_CR20","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1080\/10556788.2017.1350177","volume":"32","author":"V Guigues","year":"2017","unstructured":"Guigues, V., Juditsky, A., Nemirovski, A.: Non-asymptotic confidence bounds for the optimal value of a stochastic program. Optim. Methods Softw. 32(5), 1033\u20131058 (2017)","journal-title":"Optim. Methods Softw."},{"issue":"3","key":"1627_CR21","doi-asserted-by":"publisher","first-page":"849","DOI":"10.1287\/opre.2017.1698","volume":"66","author":"GA Hanasusanto","year":"2018","unstructured":"Hanasusanto, G.A., Kuhn, D.: Conic programming reformulations of two-stage distributionally robust linear programs over Wasserstein balls. Oper. Res. 66(3), 849\u2013869 (2018)","journal-title":"Oper. Res."},{"key":"1627_CR22","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s10107-015-0896-z","volume":"151","author":"GA Hanasusanto","year":"2015","unstructured":"Hanasusanto, G.A., Roitch, V., Kuhn, D., Wiesemann, W.: A distributionally robust perspective on uncertainty quantification and chance constrained programming. Math. Program. 151, 35\u201362 (2015)","journal-title":"Math. Program."},{"issue":"3","key":"1627_CR23","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1287\/opre.2016.1583","volume":"65","author":"GA Hanasusanto","year":"2017","unstructured":"Hanasusanto, G.A., Roitch, V., Kuhn, D., Wiesemann, W.: Ambiguous joint chance constraints under mean and dispersion information. Oper. Res. 65(3), 751\u2013767 (2017)","journal-title":"Oper. Res."},{"issue":"3","key":"1627_CR24","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0166-218X(79)90044-1","volume":"1","author":"W-L Hsu","year":"1979","unstructured":"Hsu, W.-L., Nemhauser, G.L.: Easy and hard bottleneck location problems. Discrete Appl. Math. 1(3), 209\u2013215 (1979)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"1627_CR25","doi-asserted-by":"publisher","first-page":"1390","DOI":"10.1287\/opre.2018.1729","volume":"66","author":"R Jiang","year":"2018","unstructured":"Jiang, R., Guan, Y.: Risk-averse two-stage stochastic program with distributional ambiguity. Oper. Res. 66(5), 1390\u20131405 (2018)","journal-title":"Oper. Res."},{"key":"1627_CR26","unstructured":"Kaibel, V., Peinhardt, M.: On the bottleneck shortest path problem (2006)"},{"issue":"9","key":"1627_CR27","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1016\/j.ijar.2011.01.003","volume":"52","author":"A Kasperski","year":"2011","unstructured":"Kasperski, A., Zieli\u0144ski, P.: Possibilistic bottleneck combinatorial optimization problems with ill-known weights. Int. J. Approx. Reason. 52(9), 1298\u20131311 (2011)","journal-title":"Int. J. Approx. Reason."},{"issue":"6","key":"1627_CR28","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1016\/j.orl.2013.08.014","volume":"41","author":"A Kasperski","year":"2013","unstructured":"Kasperski, A., Zieli\u0144ski, P.: Bottleneck combinatorial optimization problems with uncertain costs and the Owa criterion. Oper. Res. Lett. 41(6), 639\u2013643 (2013)","journal-title":"Oper. Res. Lett."},{"key":"1627_CR29","doi-asserted-by":"crossref","unstructured":"Kuhn, D., Esfahani, P.M., Nguyen, V.A., Shafieezadeh-Abadeh, S.: Wasserstein distributionally robust optimization: Theory and applications in machine learning. In: Operations Research & Management Science in the Age of Analytics, pp. 130\u2013166. INFORMS (2019)","DOI":"10.1287\/educ.2019.0198"},{"issue":"4","key":"1627_CR30","first-page":"1090","volume":"67","author":"H Lam","year":"2019","unstructured":"Lam, H.: Recovering best statistical guarantees via the empirical divergence-based distributionally robust optimization. Oper. Res. 67(4), 1090\u20131105 (2019)","journal-title":"Oper. Res."},{"key":"1627_CR31","doi-asserted-by":"crossref","unstructured":"Liu, X., Ravindran, K., Loguinov, D.: Multi-hop probing asymptotics in available bandwidth estimation: stochastic analysis. In: Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, pp. 15\u201315. USENIX Association (2005)","DOI":"10.1145\/1330107.1330127"},{"issue":"16","key":"1627_CR32","doi-asserted-by":"publisher","first-page":"6674","DOI":"10.1016\/j.eswa.2013.06.019","volume":"40","author":"S Martin","year":"2013","unstructured":"Martin, S., Ouelhadj, D., Smet, P., Berghe, G.V., \u00d6Zcan, E.: Cooperative search for fair nurse rosters. Expert Syst. Appl. 40(16), 6674\u20136683 (2013)","journal-title":"Expert Syst. Appl."},{"issue":"1","key":"1627_CR33","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1287\/opre.2013.1212","volume":"62","author":"K Natarajan","year":"2013","unstructured":"Natarajan, K., Shi, D., Toh, K.-C.: A probabilistic model for minmax regret in combinatorial optimization. Oper. Res. 62(1), 160\u2013181 (2013)","journal-title":"Oper. Res."},{"issue":"1","key":"1627_CR34","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1186\/s12910-017-0186-9","volume":"18","author":"B Parent","year":"2017","unstructured":"Parent, B., Caplan, A.L.: Fair is fair: We must re-allocate livers for transplant. BMC Med. Ethics 18(1), 26 (2017)","journal-title":"BMC Med. Ethics"},{"key":"1627_CR35","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.ins.2018.06.016","volume":"462","author":"F P\u00e9rez-Galarce","year":"2018","unstructured":"P\u00e9rez-Galarce, F., Candia-V\u00e9jar, A., Astudillo, C., Bardeen, M.: Algorithms for the minmax regret path problem with interval data. Inf. Sci. 462, 218\u2013241 (2018)","journal-title":"Inf. Sci."},{"issue":"2","key":"1627_CR36","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1051\/ro\/1996300201271","volume":"30","author":"U Pferschy","year":"1996","unstructured":"Pferschy, U.: The random linear bottleneck assignment problem. RAIRO-Oper. Res. 30(2), 127\u2013142 (1996)","journal-title":"RAIRO-Oper. Res."},{"key":"1627_CR37","unstructured":"Rahimian, H., Mehrotra, S.: Distributionally robust optimization: a review. Optimization Online (2019)"},{"key":"1627_CR38","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Berlin (2003)"},{"issue":"2","key":"1627_CR39","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1287\/ijoc.2014.0627","volume":"27","author":"S Shen","year":"2015","unstructured":"Shen, S., Kurt, M., Wang, J.: Chance-constrained programming models and approximations for general stochastic bottleneck spanning tree problems. INFORMS J. Comput. 27(2), 301\u2013316 (2015)","journal-title":"INFORMS J. Comput."},{"key":"1627_CR40","unstructured":"Shinn, T., Takaoka, T.: Efficient graph algorithms for network analysis. In: 1st International Conference on Resource Efficiency in Interorganizational Networks-ResEff 2013, p. 236 (2013)"},{"issue":"2","key":"1627_CR41","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1287\/moor.1110.0493","volume":"36","author":"MZ Spivey","year":"2011","unstructured":"Spivey, M.Z.: Asymptotic moments of the bottleneck assignment problem. Math. Oper. Res. 36(2), 205\u2013226 (2011)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1627_CR42","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF02564715","volume":"7","author":"I Stancu-Minasian","year":"1999","unstructured":"Stancu-Minasian, I., Caballero, R., Cerd\u00e1, E., Mu\u00f1oz, M.: The stochastic bottleneck linear programming problem. Top 7(1), 123\u2013143 (1999)","journal-title":"Top"},{"issue":"6","key":"1627_CR43","doi-asserted-by":"publisher","first-page":"1358","DOI":"10.4153\/CJM-2014-044-6","volume":"67","author":"NG Trillos","year":"2015","unstructured":"Trillos, N.G., Slep\u010dev, D.: On the rate of convergence of empirical measures in $$\\infty $$ transportation distance. Can. J. Math. 67(6), 1358\u20131383 (2015)","journal-title":"Can. J. Math."},{"key":"1627_CR44","doi-asserted-by":"crossref","unstructured":"Xie, W.: On distributionally robust chance constrained programs with Wasserstein distance. Math. Program. 1\u201341 (2019)","DOI":"10.1007\/s10107-019-01445-5"},{"key":"1627_CR45","unstructured":"Xie, W.: Tractable reformulations of distributionally robust two-stage stochastic programs with $$\\infty -$$ Wasserstein distance. arXiv preprint arXiv:1908.08454 (2019)"},{"issue":"2","key":"1627_CR46","doi-asserted-by":"publisher","first-page":"1151","DOI":"10.1137\/16M1094725","volume":"28","author":"W Xie","year":"2018","unstructured":"Xie, W., Ahmed, S.: On deterministic reformulations of distributionally robust joint chance constrained optimization problems. SIAM J. Optim. 28(2), 1151\u20131182 (2018)","journal-title":"SIAM J. Optim."},{"key":"1627_CR47","doi-asserted-by":"crossref","unstructured":"Yoo, J.-Y., Kim, J.: Maximum end-to-end throughput of chain-topology wireless multi-hop networks. In: 2007 IEEE Wireless Communications and Networking Conference, pp. 4279\u20134283. IEEE (2007)","DOI":"10.1109\/WCNC.2007.781"},{"key":"1627_CR48","doi-asserted-by":"crossref","unstructured":"Zhang, L., Chen, S., Jian, Y.: Achieving global end-to-end maxmin in multihop wireless networks. In: 2008 The 28th International Conference on Distributed Computing Systems, pp. 225\u2013232. IEEE (2008)","DOI":"10.1109\/ICDCS.2008.66"},{"key":"1627_CR49","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10107-011-0494-7","volume":"137","author":"S Zymler","year":"2013","unstructured":"Zymler, S., Kuhn, D., Rustem, B.: Distributionally robust joint chance constraints with second-order moment information. Math. Program. 137, 167\u2013198 (2013)","journal-title":"Math. Program."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01627-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01627-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01627-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T05:06:45Z","timestamp":1667884005000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01627-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,22]]},"references-count":49,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1627"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01627-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,22]]},"assertion":[{"value":"28 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}