{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:36:01Z","timestamp":1770896161727,"version":"3.50.1"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,5,30]],"date-time":"2022-05-30T00:00:00Z","timestamp":1653868800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,30]],"date-time":"2022-05-30T00:00:00Z","timestamp":1653868800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"twosigma","award":["TwoSigma PhD Fellowship"],"award-info":[{"award-number":["TwoSigma PhD Fellowship"]}]},{"name":"National Science Foundation","award":["NSF AF 1565235"],"award-info":[{"award-number":["NSF AF 1565235"]}]},{"name":"National Science Foundation","award":["NSF Graduate Research Fellowship"],"award-info":[{"award-number":["NSF Graduate Research Fellowship"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,3]]},"abstract":"Abstract<\/jats:title>We revisit Matrix Balancing, a pre-conditioning task used ubiquitously for computing eigenvalues and matrix exponentials. Since 1960, Osborne\u2019s algorithm has been the practitioners\u2019 algorithm of choice, and is now implemented in most numerical software packages. However, the theoretical properties of Osborne\u2019s algorithm are not well understood. Here, we show that a simple random variant of Osborne\u2019s algorithm converges in near-linear time in the input sparsity. Specifically, it balances $$K \\in {\\mathbb {R}}_{\\ge 0}^{n \\times n}$$<\/jats:tex-math>\n \n K<\/mml:mi>\n \u2208<\/mml:mo>\n \n R<\/mml:mi>\n \n \u2265<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n \n n<\/mml:mi>\n \u00d7<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msubsup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> after $$O(m \\varepsilon ^{-2} \\log \\kappa )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n m<\/mml:mi>\n \n \u03b5<\/mml:mi>\n \n -<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n log<\/mml:mo>\n \u03ba<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> arithmetic operations in expectation and with high probability, where m<\/jats:italic> is the number of nonzeros in K<\/jats:italic>, $$\\varepsilon $$<\/jats:tex-math>\n \u03b5<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the $$\\ell _1$$<\/jats:tex-math>\n \n \u2113<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> accuracy, and $$\\kappa = \\sum _{ij} K_{ij} \/ ( \\min _{ij : K_{ij} \\ne 0} K_{ij})$$<\/jats:tex-math>\n \n \u03ba<\/mml:mi>\n =<\/mml:mo>\n \n \u2211<\/mml:mo>\n \n ij<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \n K<\/mml:mi>\n \n ij<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \/<\/mml:mo>\n \n (<\/mml:mo>\n \n min<\/mml:mo>\n \n i<\/mml:mi>\n j<\/mml:mi>\n :<\/mml:mo>\n \n K<\/mml:mi>\n \n ij<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n \u2260<\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n \n K<\/mml:mi>\n \n ij<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> measures the conditioning of K<\/jats:italic>. Previous work had established near-linear runtimes either only for $$\\ell _2$$<\/jats:tex-math>\n \n \u2113<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> accuracy (a weaker criterion which is less relevant for applications), or through an entirely different algorithm based on (currently) impractical Laplacian solvers. We further show that if the graph with adjacency matrix K<\/jats:italic> is moderately connected\u2014e.g., if K<\/jats:italic> has at least one positive row\/column pair\u2014then Osborne\u2019s algorithm initially converges exponentially fast, yielding an improved runtime $$O(m \\varepsilon ^{-1} \\log \\kappa )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n m<\/mml:mi>\n \n \u03b5<\/mml:mi>\n \n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n log<\/mml:mo>\n \u03ba<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We also address numerical precision issues by showing that these runtime bounds still hold when using $$O(\\log (n\\kappa \/\\varepsilon ))$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n (<\/mml:mo>\n n<\/mml:mi>\n \u03ba<\/mml:mi>\n \/<\/mml:mo>\n \u03b5<\/mml:mi>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-bit numbers. Our results are established through an intuitive potential argument that leverages a convex optimization perspective of Osborne\u2019s algorithm, and relates the per-iteration progress to the current imbalance as measured in Hellinger distance. Unlike previous analyses, we critically exploit log-convexity of the potential. Notably, our analysis extends to other variants of Osborne\u2019s algorithm: along the way, we also establish significantly improved runtime bounds for cyclic, greedy, and parallelized variants of Osborne\u2019s algorithm.<\/jats:p>","DOI":"10.1007\/s10107-022-01825-4","type":"journal-article","created":{"date-parts":[[2022,5,30]],"date-time":"2022-05-30T12:09:42Z","timestamp":1653912582000},"page":"363-397","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Near-linear convergence of the Random Osborne algorithm for Matrix Balancing"],"prefix":"10.1007","volume":"198","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7367-0097","authenticated-orcid":false,"given":"Jason M.","family":"Altschuler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pablo A.","family":"Parrilo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,30]]},"reference":[{"key":"1825_CR1","doi-asserted-by":"crossref","unstructured":"Allen-Zhu, Z., Li, Y., Oliveira, R., Wigderson, A.: Much faster algorithms for matrix scaling. In: Symposium on the Foundations of Computer Science (FOCS). IEEE (2017)","DOI":"10.1109\/FOCS.2017.87"},{"key":"1825_CR2","unstructured":"Allen-Zhu, Z., Qu, Z., Richt\u00e1rik, P., Yuan, Y.: Even faster accelerated coordinate descent using non-uniform sampling. In: International Conference on Machine Learning (ICML), pp. 1110\u20131119 (2016)"},{"key":"1825_CR3","unstructured":"Altschuler, J., Weed, J., Rigollet, P.: Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. In: Conference on Neural Information Processing Systems (NeurIPS) (2017)"},{"key":"1825_CR4","doi-asserted-by":"crossref","unstructured":"Altschuler, J.M., Parrilo, P.A.: Approximating Min-Mean-Cycle for low-diameter graphs in near-optimal time and memory. SIAM J. Optim. (2022, to appear)","DOI":"10.1137\/21M1439390"},{"key":"1825_CR5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719604","volume-title":"LAPACK Users\u2019 Guide","author":"E Anderson","year":"1999","unstructured":"Anderson, E., Bai, Z., Bischof, C., Blackford, S., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Sorensen, D.: LAPACK Users\u2019 Guide, 3rd edn. Society for Industrial and Applied Mathematics, Philadelphia, PA (1999)","edition":"3"},{"issue":"1","key":"1825_CR6","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1137\/12088848X","volume":"43","author":"L Barenboim","year":"2014","unstructured":"Barenboim, L., Elkin, M., Kuhn, F.: Distributed ($${{\\varDelta }}$$+1)-coloring in linear (in $${{\\varDelta }}$$) time. SIAM J. Comput. 43(1), 72\u201395 (2014)","journal-title":"SIAM J. Comput."},{"key":"1825_CR7","volume-title":"Parallel and Distributed Computation: Numerical Methods","author":"DP Bertsekas","year":"1989","unstructured":"Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation: Numerical Methods, vol. 23. Prentice Hall Englewood Cliffs, NJ (1989)"},{"key":"1825_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs, vol. 73. Cambridge University Press, Cambridge (2001)"},{"key":"1825_CR9","unstructured":"Chakrabarty, D., Khanna, S.: Better and simpler error analysis of the Sinkhorn-Knopp algorithm for matrix scaling. In: Symposium on Simplicity in Algorithms (SOSA) (2018)"},{"key":"1825_CR10","unstructured":"Chen, T.Y.: Balancing sparse matrices for computing eigenvalues. Master\u2019s thesis, UC Berkeley (1998)"},{"issue":"1\u20133","key":"1825_CR11","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0024-3795(00)00014-8","volume":"309","author":"TY Chen","year":"2000","unstructured":"Chen, T.Y., Demmel, J.W.: Balancing sparse matrices for computing eigenvalues. Linear Algebra Appl. 309(1\u20133), 261\u2013287 (2000)","journal-title":"Linear Algebra Appl."},{"key":"1825_CR12","doi-asserted-by":"crossref","unstructured":"Cohen, M.B., Madry, A., Tsipras, D., Vladu, A.: Matrix scaling and balancing via box constrained Newton\u2019s method and interior point methods. In: Symposium on the Foundations of Computer Science (FOCS), pp. 902\u2013913. IEEE (2017)","DOI":"10.1109\/FOCS.2017.88"},{"key":"1825_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-00234-2","volume-title":"Encyclopedia of Distances","author":"MM Deza","year":"2009","unstructured":"Deza, M.M., Deza, E.: Encyclopedia of Distances, pp. 1\u2013583. Springer, New York (2009)"},{"key":"1825_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511779398","volume-title":"Probability: Theory and Examples","author":"R Durrett","year":"2010","unstructured":"Durrett, R.: Probability: Theory and Examples. Cambridge University Press, Cambridge (2010)"},{"key":"1825_CR15","unstructured":"Dvurechensky, P., Gasnikov, A., Kroshnin, A.: Computational optimal transport: complexity by accelerated gradient descent is better than by Sinkhorn\u2019s algorithm. In: International Conference on Machine Learning (ICML) (2018)"},{"key":"1825_CR16","doi-asserted-by":"crossref","unstructured":"Eaves, B.C., Hoffman, A.J., Rothblum, U.G., Schneider, H.: Line-sum-symmetric scalings of square nonnegative matrices. In: Mathematical Programming Essays in Honor of George B. Dantzig Part II, pp. 124\u2013141. Springer (1985)","DOI":"10.1007\/BFb0121080"},{"issue":"1","key":"1825_CR17","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/321921.321926","volume":"23","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S.: The complexity of near-optimal graph coloring. J. ACM 23(1), 43\u201349 (1976)","journal-title":"J. ACM"},{"key":"1825_CR18","unstructured":"Goulet, V., Dutang, C., Maechler, M., Firth, D., Shapira, M., Stadelmann, M., et\u00a0al.: expm: Matrix exponential. R package version 0.99-0 (2013)"},{"key":"1825_CR19","unstructured":"Gurvits, L., Yianilos, P.N.: The deflation-inflation method for certain semidefinite programming and maximum determinant completion problems. Technical report, NECI (1998)"},{"issue":"4","key":"1825_CR20","doi-asserted-by":"publisher","first-page":"1179","DOI":"10.1137\/04061101X","volume":"26","author":"NJ Higham","year":"2005","unstructured":"Higham, N.J.: The scaling and squaring method for the matrix exponential revisited. SIAM J. Matrix Anal. Appl. 26(4), 1179\u20131193 (2005)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1825_CR21","unstructured":"Idel, M.: A review of matrix scaling and Sinkhorn\u2019s normal form for matrices and positive maps. arXiv preprint arXiv:1609.06349 (2016)"},{"issue":"2","key":"1825_CR22","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/S0895479895289765","volume":"18","author":"B Kalantari","year":"1997","unstructured":"Kalantari, B., Khachiyan, L., Shokoufandeh, A.: On the complexity of matrix balancing. SIAM J. Matrix Anal. Appl. 18(2), 450\u2013463 (1997)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1825_CR23","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103. Springer (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"1825_CR24","doi-asserted-by":"publisher","first-page":"1246","DOI":"10.1093\/imanum\/dry040","volume":"39","author":"CP Lee","year":"2019","unstructured":"Lee, C.P., Wright, S.J.: Random permutations fix a worst case for cyclic coordinate descent. IMA J. Numer. Anal. 39(3), 1246\u20131275 (2019)","journal-title":"IMA J. Numer. Anal."},{"key":"1825_CR25","doi-asserted-by":"crossref","unstructured":"Mai, V.S., Battou, A.: Asynchronous distributed matrix balancing and application to suppressing epidemic. In: 2019 American Control Conference (ACC), pp. 2177\u20132182. IEEE (2019)","DOI":"10.23919\/ACC.2019.8815113"},{"key":"1825_CR26","unstructured":"MathWorks: balance: diagonal scaling to improve eigenvalue accuracy. https:\/\/www.mathworks.com\/help\/matlab\/ref\/balance.html"},{"key":"1825_CR27","unstructured":"MathWorks: eig: eigenvalues and eigenvectors. https:\/\/www.mathworks.com\/help\/matlab\/ref\/eig.html"},{"key":"1825_CR28","volume-title":"Probability and Computing: Randomization and probabilistic techniques in algorithms and data analysis","author":"M Mitzenmacher","year":"2017","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge University Press, Cambridge (2017)"},{"key":"1825_CR29","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/S0024-3795(99)00212-8","volume":"302","author":"A Nemirovski","year":"1999","unstructured":"Nemirovski, A., Rothblum, U.: On complexity of matrix scaling. Linear Algebra Appl. 302, 435\u2013460 (1999)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"1825_CR30","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1137\/16M1060182","volume":"27","author":"Y Nesterov","year":"2017","unstructured":"Nesterov, Y., Stich, S.U.: Efficiency of the accelerated coordinate descent method on structured optimization problems. SIAM J. Optim. 27(1), 110\u2013123 (2017)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"1825_CR31","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1145\/321043.321048","volume":"7","author":"E Osborne","year":"1960","unstructured":"Osborne, E.: On pre-conditioning of matrices. J. ACM 7(4), 338\u2013345 (1960)","journal-title":"J. ACM"},{"key":"1825_CR32","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y., Yousefi, A.: Matrix balancing in $$l_p$$ norms: bounding the convergence rate of Osborne\u2019s iteration. In: Symposium on Discrete Algorithms (SODA), pp. 154\u2013169. SIAM (2017)","DOI":"10.1137\/1.9781611974782.11"},{"key":"1825_CR33","unstructured":"Ostrovsky, R., Rabani, Y., Yousefi, A.: Strictly balancing matrices in polynomial time using Osborne\u2019s iteration. In: International Colloquium on Automata, Languages and Programming (ICALP) (2018)"},{"issue":"4","key":"1825_CR34","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/BF02165404","volume":"13","author":"BN Parlett","year":"1969","unstructured":"Parlett, B.N., Reinsch, C.: Balancing a matrix for calculation of eigenvalues and eigenvectors. Numerische Mathematik 13(4), 293\u2013304 (1969)","journal-title":"Numerische Mathematik"},{"key":"1825_CR35","volume-title":"Numerical recipes 3rd edition: the art of scientific computing","author":"WH Press","year":"2007","unstructured":"Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical recipes 3rd edition: the art of scientific computing. Cambridge University Press, Cambridge (2007)"},{"key":"1825_CR36","unstructured":"RDocumentation: Balance a square matrix via LAPACK\u2019s dgebal. https:\/\/www.rdocumentation.org\/packages\/expm\/versions\/0.99-1.1\/topics\/balance"},{"issue":"1","key":"1825_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0895479891222088","volume":"15","author":"UG Rothblum","year":"1994","unstructured":"Rothblum, U.G., Schneider, H., Schneider, M.H.: Scaling matrices to prescribed row and column maxima. SIAM J. Matrix Anal. Appl. 15(1), 1\u201314 (1994)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"1","key":"1825_CR38","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1287\/moor.16.1.208","volume":"16","author":"H Schneider","year":"1991","unstructured":"Schneider, H., Schneider, M.H.: Max-balancing weighted directed graphs and matrix scaling. Math. Oper. Res. 16(1), 208\u2013222 (1991)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1825_CR39","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1287\/opre.38.3.439","volume":"38","author":"MH Schneider","year":"1990","unstructured":"Schneider, M.H., Zenios, S.A.: A comparative study of algorithms for matrix balancing. Oper. Res. 38(3), 439\u2013455 (1990)","journal-title":"Oper. Res."},{"issue":"2","key":"1825_CR40","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2988227","volume":"64","author":"LJ Schulman","year":"2017","unstructured":"Schulman, L.J., Sinclair, A.: Analysis of a classical matrix preconditioning algorithm. J. ACM 64(2), 9 (2017)","journal-title":"J. ACM"},{"issue":"4","key":"1825_CR41","doi-asserted-by":"publisher","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. Am. Math. Mon. 74(4), 402\u2013405 (1967)","journal-title":"Am. Math. Mon."},{"key":"1825_CR42","volume-title":"Matrix Eigensystem Routines - EISPACK Guide","author":"BT Smith","year":"2013","unstructured":"Smith, B.T., Boyle, J.M., Garbow, B., Ikebe, Y., Klema, V., Moler, C.: Matrix Eigensystem Routines - EISPACK Guide, vol. 6. Springer, New York (2013)"},{"issue":"1","key":"1825_CR43","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.2019.0990","volume":"45","author":"R Sun","year":"2020","unstructured":"Sun, R., Luo, Z.Q., Ye, Y.: On the efficiency of random permutation for ADMM and coordinate descent. Math. Oper. Res. 45(1), 233\u2013271 (2020)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1825_CR44","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s10107-019-01437-5","volume":"185","author":"R Sun","year":"2021","unstructured":"Sun, R., Ye, Y.: Worst-case complexity of cyclic coordinate descent: $${O}(n^2)$$ gap with randomized version. Math. Prog. 185(1), 487\u2013520 (2021)","journal-title":"Math. Prog."},{"issue":"2","key":"1825_CR45","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"1825_CR46","doi-asserted-by":"crossref","unstructured":"Tomlin, J.A.: A new paradigm for ranking pages on the world wide web. In: Proceedings of the 12th international conference on World Wide Web, pp. 350\u2013355 (2003)","DOI":"10.1145\/775152.775202"},{"issue":"4","key":"1825_CR47","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1137\/0714039","volume":"14","author":"RC Ward","year":"1977","unstructured":"Ward, R.C.: Numerical computation of the matrix exponential with accuracy estimate. SIAM J. Numer. Anal. 14(4), 600\u2013610 (1977)","journal-title":"SIAM J. Numer. Anal."},{"issue":"1","key":"1825_CR48","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10107-015-0892-3","volume":"151","author":"SJ Wright","year":"2015","unstructured":"Wright, S.J.: Coordinate descent algorithms. Math. Progr. 151(1), 3\u201334 (2015)","journal-title":"Math. Progr."},{"issue":"2","key":"1825_CR49","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/net.3230210206","volume":"21","author":"NE Young","year":"1991","unstructured":"Young, N.E., Tarjan, R.E., Orlin, J.B.: Faster parametric shortest path and minimum-balance algorithms. Networks 21(2), 205\u2013221 (1991)","journal-title":"Networks"},{"key":"1825_CR50","doi-asserted-by":"crossref","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. In: Symposium on the Theory of Computing (STOC), pp. 681\u2013690. ACM (2006)","DOI":"10.1145\/1132516.1132612"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01825-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01825-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01825-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T22:22:37Z","timestamp":1677018157000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01825-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,30]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["1825"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01825-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,30]]},"assertion":[{"value":"6 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2022","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 declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}