{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,14]],"date-time":"2026-07-14T17:52:06Z","timestamp":1784051526706,"version":"3.55.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T00:00:00Z","timestamp":1736294400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T00:00:00Z","timestamp":1736294400000},"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":["Math. Prog. Comp."],"published-print":{"date-parts":[[2025,6]]},"DOI":"10.1007\/s12532-024-00273-9","type":"journal-article","created":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T06:53:08Z","timestamp":1736319188000},"page":"307-348","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On O(n) algorithms for projection onto the top-k-sum sublevel set"],"prefix":"10.1007","volume":"17","author":[{"given":"Jake","family":"Roth","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"Cui","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,1,8]]},"reference":[{"key":"273_CR1","unstructured":"Alexandrescu, A.: Fast deterministic selection. In: Iliopoulos, C.S., Pissis, S.P., Puglisi, S.J., Raman, R. (eds.) 16th International Symposium on Experimental Algorithms (SEA 2017), volume\u00a075 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 24:1\u201324:19, Dagstuhl, Germany, 2017. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"2\u20133","key":"273_CR2","doi-asserted-by":"publisher","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. Trends Mach. Learn. 6(2\u20133), 145\u2013373 (2013)","journal-title":"Found. Trends Mach. Learn."},{"issue":"337","key":"273_CR3","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1080\/01621459.1972.10481216","volume":"67","author":"RE Barlow","year":"1972","unstructured":"Barlow, R.E., Brunk, H.D.: The isotonic regression problem and its dual. J. Am. Stat. Assoc. 67(337), 140\u2013147 (1972)","journal-title":"J. Am. Stat. Assoc."},{"issue":"1","key":"273_CR4","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1007\/BF01580873","volume":"47","author":"MJ Best","year":"1990","unstructured":"Best, M.J., Chakravarti, N.: Active set algorithms for isotonic regression; a unifying framework. Math. Prog. 47(1), 425\u2013439 (1990)","journal-title":"Math. Prog."},{"issue":"1","key":"273_CR5","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1137\/141000671","volume":"59","author":"J Bezanson","year":"2017","unstructured":"Bezanson, J., Edelman, A., Karpinski, S., Shah, V.B.: Julia: a fresh approach to numerical computing. SIAM Rev. 59(1), 65\u201398 (2017)","journal-title":"SIAM Rev."},{"key":"273_CR6","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. 7, 448\u2013461 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"273_CR7","first-page":"263","volume":"7","author":"R Chandrasekaran","year":"1970","unstructured":"Chandrasekaran, R.: A special case of the complementary pivot problem. Opsearch 7, 263\u2013268 (1970)","journal-title":"Opsearch"},{"issue":"2","key":"273_CR8","doi-asserted-by":"publisher","first-page":"551","DOI":"10.2514\/1.J060539","volume":"60","author":"A Chaudhuri","year":"2022","unstructured":"Chaudhuri, A., Kramer, B., Norton, M., Royset, J.O., Willcox, K.: Certifiable risk-based engineering design optimization. Am. Inst. Aeronaut. Astronaut. J. 60(2), 551\u2013565 (2022)","journal-title":"Am. Inst. Aeronaut. Astronaut. J."},{"issue":"2","key":"273_CR9","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1287\/opre.1090.0712","volume":"58","author":"W Chen","year":"2010","unstructured":"Chen, W., Sim, M., Sun, J., Teo, C.-P.: From CVaR to uncertainty set: Implications in joint chance-constrained optimization. Oper. Res. 58(2), 470\u2013485 (2010)","journal-title":"Oper. Res."},{"key":"273_CR10","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1007\/s10107-015-0946-6","volume":"158","author":"L Condat","year":"2016","unstructured":"Condat, L.: Fast projection onto the simplex and $$\\ell _1$$ ball. Math. Program. Ser. A 158, 575\u2013585 (2016)","journal-title":"Math. Program. Ser. A"},{"issue":"1","key":"273_CR11","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1007\/BF01584990","volume":"3","author":"RW Cottle","year":"1972","unstructured":"Cottle, R.W.: Monotone solutions of the parametric linear complementarity problem. Math. Prog. 3(1), 210\u2013224 (1972)","journal-title":"Math. Prog."},{"key":"273_CR12","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719000","volume-title":"The Linear Complementarity Problem","author":"RW Cottle","year":"2009","unstructured":"Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. SIAM, Philadelphia (2009)"},{"key":"273_CR13","unstructured":"Cucala, D.T., Grau, B.C., Motik, B., Kostylev, E.V.: On the correspondence between monotonic max-sum GNNs and datalog (2023). arXiv:2305.18015"},{"issue":"2","key":"273_CR14","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1109\/TPWRS.2003.810685","volume":"18","author":"R Dahlgren","year":"2003","unstructured":"Dahlgren, R., Liu, C.-C., Lawarr\u00e9e, J.: Risk assessment in energy trading. IEEE Trans. Power Syst. 18(2), 503\u2013511 (2003)","journal-title":"IEEE Trans. Power Syst."},{"key":"273_CR15","unstructured":"Davis., D.: An $$O(n \\log (n))$$ algorithm for projecting onto the ordered weighted $$\\ell _1$$ norm ball (2015). arXiv:1505.00870"},{"key":"273_CR16","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.applthermaleng.2017.05.069","volume":"123","author":"A Dolatabadi","year":"2017","unstructured":"Dolatabadi, A., Mohammadi-Ivatloo, B.: Stochastic risk-constrained scheduling of smart energy hub in the presence of wind power and demand response. Appl. Therm. Eng. 123, 40\u201349 (2017)","journal-title":"Appl. Therm. Eng."},{"key":"273_CR17","doi-asserted-by":"crossref","unstructured":"Eigen, H., Sadovnik, A.: TopKConv: Increased adversarial robustness through deeper interpretability. In: 20th IEEE International Conference on Machine Learning and Applications (ICMLA), pp. 15\u201322 (2021)","DOI":"10.1109\/ICMLA52953.2021.00011"},{"key":"273_CR18","unstructured":"Figueiredo, M.A.T., Zeng, X.: The ordered weighted $$\\ell _1$$ norm: atomic formulation, projections, and algorithms (2014). arXiv:1409.4271"},{"key":"273_CR19","unstructured":"Fr\u00f6hlich, C., Williamson, R.C.: Risk measures and upper probabilities: coherence and stratification (2022). arXiv:2206.03183"},{"issue":"2","key":"273_CR20","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1287\/moor.20.2.441","volume":"20","author":"O G\u00fcler","year":"1995","unstructured":"G\u00fcler, O.: Generalized linear complementarity problems. Math. Oper. Res. 20(2), 441\u2013448 (1995)","journal-title":"Math. Oper. Res."},{"key":"273_CR21","first-page":"321","volume":"4","author":"CAR Hoare","year":"1961","unstructured":"Hoare, C.A.R.: Algorithm 65: find. Commun. ACM 4, 321\u2013322 (1961)","journal-title":"Commun. ACM"},{"key":"273_CR22","doi-asserted-by":"crossref","unstructured":"Hu, S., Wang, X., Lyu, S.: Rank-based decomposable losses in machine learning: a survey. IEEE Trans. Pattern Anal. Mach. Intell. PP (2023)","DOI":"10.1109\/TPAMI.2023.3296062"},{"issue":"6","key":"273_CR23","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/BF01195027","volume":"46","author":"G Isac","year":"1986","unstructured":"Isac, G., N\u00e9meth, A.B.: Monotonicity of metric projections onto positive cones of ordered Euclidean spaces. Arch. Math. 46(6), 568\u2013576 (1986)","journal-title":"Arch. Math."},{"issue":"5","key":"273_CR24","doi-asserted-by":"publisher","first-page":"3764","DOI":"10.1109\/TPWRS.2020.2971684","volume":"35","author":"RA Jabr","year":"2020","unstructured":"Jabr, R.A.: Distributionally robust CVaR constraints for power flow optimization. IEEE Trans. Power Syst. 35(5), 3764\u20133773 (2020)","journal-title":"IEEE Trans. Power Syst."},{"key":"273_CR25","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1007\/s11228-021-00609-w","volume":"29","author":"Y Laguel","year":"2021","unstructured":"Laguel, Y., Pillutla, K., Malick, J., Harchaoui, Z.: Superquantiles at work: machine learning applications and efficient subgradient computation. Set-Valued Var. Anal. 29, 967\u2013996 (2021)","journal-title":"Set-Valued Var. Anal."},{"key":"273_CR26","first-page":"15029","volume":"32","author":"L Leqi","year":"2019","unstructured":"Leqi, L., Prasad, A., Ravikumar, P.K.: On human-aligned risk minimization. Adv. Neural Inf. Process. Syst. 32, 15029\u201315038 (2019)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"273_CR27","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1007\/s11425-020-1743-9","volume":"65","author":"Q Li","year":"2021","unstructured":"Li, Q., Li, X.: Fast projection onto the ordered weighted $$\\ell _1$$ norm ball. Sci. China Math. 65, 869\u2013886 (2021)","journal-title":"Sci. China Math."},{"key":"273_CR28","unstructured":"N\u00e9meth, A.B., N\u00e9meth, S.Z.: Isotonicity of the projection onto the monotone cone (2012). arXiv:1201.4677"},{"issue":"4","key":"273_CR29","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1137\/050622328","volume":"17","author":"A Nemirovski","year":"2006","unstructured":"Nemirovski, A., Shapiro, A.: Convex approximations of chance constrained programs. SIAM J. Optim. 17(4), 969\u2013996 (2006)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"273_CR30","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF01585173","volume":"62","author":"ML Overton","year":"1993","unstructured":"Overton, M.L., Womersley, R.S.: Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices. Math. Prog. 62(1), 321\u2013357 (1993)","journal-title":"Math. Prog."},{"issue":"4","key":"273_CR31","doi-asserted-by":"publisher","first-page":"927","DOI":"10.1287\/opre.28.4.927","volume":"28","author":"J-S Pang","year":"1980","unstructured":"Pang, J.-S.: A parametric linear complementarity technique for optimal portfolio selection with a risk-free asset. Oper. Res. 28(4), 927\u2013941 (1980)","journal-title":"Oper. Res."},{"key":"273_CR32","unstructured":"Peng, L., Travadi, Y., Zhang, R., Cui, Y., Sun, J.: Imbalanced classification in medical imaging via regrouping (2022). arXiv:2210.12234"},{"key":"273_CR33","unstructured":"Robey, A., Chamon, L., Pappas, G.J., Hassani, H.: Probabilistically robust learning: Balancing average and worst-case performance. In: Proceedings of the 39th International Conference on Machine Learning, vol. 162, pp. 18667\u201318686. PMLR (2022)"},{"issue":"3","key":"273_CR34","doi-asserted-by":"publisher","first-page":"21","DOI":"10.21314\/JOR.2000.038","volume":"2","author":"RT Rockafellar","year":"1999","unstructured":"Rockafellar, R.T., Uryasev, S.: Optimization of conditional value-at-risk. J. Risk 2(3), 21\u201341 (1999)","journal-title":"J. Risk"},{"key":"273_CR35","doi-asserted-by":"publisher","unstructured":"Roth, J., Cui, Y.: Top-k-sum.jl. https:\/\/doi.org\/10.5281\/zenodo.14189753","DOI":"10.5281\/zenodo.14189753"},{"key":"273_CR36","unstructured":"Roth, J., Cui, Y.: Fast computation of superquantile-constrained optimization through implicit scenario reduction (2023). arXiv:2405.07965"},{"key":"273_CR37","unstructured":"Royset, J.O.: Risk-adaptive approaches to learning and decision making: a survey (2022). arXiv:2212.00856"},{"key":"273_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ijepes.2018.02.022","volume":"100","author":"M Tavakoli","year":"2018","unstructured":"Tavakoli, M., Shokridehaki, F., Funsho Akorede, M., Marzband, M., Vechiu, I., Pouresmaeil, E.: CVaR-based energy management scheme for optimal resilience and operational cost in commercial building microgrids. Int. J. Electr. Power Energy Syst. 100, 1\u20139 (2018)","journal-title":"Int. J. Electr. Power Energy Syst."},{"issue":"1\u20132","key":"273_CR39","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s10107-017-1201-0","volume":"171","author":"MJ Todd","year":"2018","unstructured":"Todd, M.J.: On max-k-sums. Math. Prog. 171(1\u20132), 489\u2013517 (2018)","journal-title":"Math. Prog."},{"key":"273_CR40","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1145\/512274.3734138","volume":"7","author":"JWJ Williams","year":"1964","unstructured":"Williams, J.W.J.: Algorithm 232: heapsort. Commun. ACM 7, 347\u2013348 (1964)","journal-title":"Commun. ACM"},{"key":"273_CR41","unstructured":"Williamson, R.C., Menon, A.: Fairness risk measures. In: Proceedings of the 36th International Conference on Machine Learning, vol.\u00a097, pp. 6786\u20136797. PMLR (2019)"},{"issue":"2","key":"273_CR42","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1137\/110827144","volume":"24","author":"B Wu","year":"2014","unstructured":"Wu, B., Ding, C., Sun, D., Toh, K.-C.: On the Moreau-Yosida regularization of the vector $$k$$-norm related functions. SIAM J. Optim. 24(2), 766\u2013794 (2014)","journal-title":"SIAM J. Optim."},{"key":"273_CR43","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.neucom.2020.01.104","volume":"395","author":"P Yuan","year":"2020","unstructured":"Yuan, P., You, X., Chen, H., Peng, Q., Zhao, Y., Xu, Z., Jing, X.-Y., He, Z.: Group sparse additive machine with average top-k loss. Neurocomputing 395, 1\u201314 (2020)","journal-title":"Neurocomputing"}],"container-title":["Mathematical Programming Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-024-00273-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12532-024-00273-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12532-024-00273-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T11:23:22Z","timestamp":1747394602000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12532-024-00273-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,8]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["273"],"URL":"https:\/\/doi.org\/10.1007\/s12532-024-00273-9","relation":{},"ISSN":["1867-2949","1867-2957"],"issn-type":[{"value":"1867-2949","type":"print"},{"value":"1867-2957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,8]]},"assertion":[{"value":"11 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}