{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:24:26Z","timestamp":1725888266951},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319592497"},{"type":"electronic","value":"9783319592503"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-59250-3_22","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T13:04:39Z","timestamp":1495544679000},"page":"267-278","source":"Crossref","is-referenced-by-count":3,"title":["An Improved Deterministic Rescaling for Linear Programming Algorithms"],"prefix":"10.1007","author":[{"given":"Rebecca","family":"Hoberg","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Rothvoss","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","first-page":"382","DOI":"10.4153\/CJM-1954-037-2","volume":"6","author":"S Agmon","year":"1954","unstructured":"Agmon, S.: The relaxation method for linear inequalities. Can. J. Math. 6, 382\u2013392 (1954)","journal-title":"Can. J. Math."},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Hazan, E., Kale, S.: Fast algorithms for approximate semidefinite programming using the multiplicative weights update method. In: 46th IEEE FOCS, pp. 339\u2013348 (2005)","DOI":"10.1109\/SFCS.2005.35"},{"key":"22_CR3","doi-asserted-by":"crossref","first-page":"121","DOI":"10.4086\/toc.2012.v008a006","volume":"8","author":"S Arora","year":"2012","unstructured":"Arora, S., Hazan, E., Kale, S.: The multiplicative weights update method: a meta-algorithm and applications. Theor. Comp. 8, 121\u2013164 (2012)","journal-title":"Theor. Comp."},{"key":"22_CR4","series-title":"Wiley Series in Discrete Mathematics and Optimization","volume-title":"The Probabilistic Method","author":"N Alon","year":"2004","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley Series in Discrete Mathematics and Optimization. Wiley, Hoboken (2004)"},{"key":"22_CR5","first-page":"1","volume-title":"Flavors of Geometry","author":"K Ball","year":"1997","unstructured":"Ball, K.: An elementary introduction to modern convex geometry. In: Silvio, L. (ed.) Flavors of Geometry, pp. 1\u201358. University Press, Cambridge (1997)"},{"issue":"3","key":"22_CR6","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s00454-004-2878-4","volume":"32","author":"U Betke","year":"2004","unstructured":"Betke, U.: Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem. Discrete Comput. Geom. 32(3), 317\u2013338 (2004)","journal-title":"Discrete Comput. Geom."},{"key":"22_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer Programming","author":"M Conforti","year":"2014","unstructured":"Conforti, M., Cornuejols, G., Zambelli, G.: Integer Programming. Springer Publishing Company Inc., Heidelberg (2014)"},{"issue":"2","key":"22_CR8","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/s10107-011-0445-3","volume":"134","author":"S Chubanov","year":"2012","unstructured":"Chubanov, S.: A strongly polynomial algorithm for linear systems having a binary solution. Math. Program. 134(2), 533\u2013570 (2012)","journal-title":"Math. Program."},{"issue":"2","key":"22_CR9","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1007\/s10107-014-0823-8","volume":"153","author":"S Chubanov","year":"2015","unstructured":"Chubanov, S.: A polynomial projection algorithm for linear feasibility problems. Math. Program. 153(2), 687\u2013713 (2015)","journal-title":"Math. Program."},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"Christiano, P., Kelner, J.A., Madry, A., Spielman, D.A., Teng, S.: Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, New York, NY, USA, pp. 273\u2013282 (2011)","DOI":"10.1145\/1993636.1993674"},{"key":"22_CR11","unstructured":"Dantzig, G.B.: Maximization of a linear function of variables subject to linear inequalities. In: Activity Analysis of Production and Allocation, Cowles Commission Monograph, vol. 13, pp. 339\u2013347. John Wiley & Sons Inc., Chapman & Hall Ltd., New York (1951)"},{"issue":"1","key":"22_CR12","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/s10107-007-0095-7","volume":"114","author":"J Dunagan","year":"2006","unstructured":"Dunagan, J., Vempala, S.: A simple polynomial-time rescaling algorithm for solving linear programs. Math. Program. 114(1), 101\u2013114 (2006)","journal-title":"Math. Program."},{"key":"22_CR13","unstructured":"Dadush, D., V\u00e9gh, L.A., Zambelli, G.: Rescaling algorithms for linear programming - part I: conic feasibility. CoRR, abs\/1611.06427 (2016)"},{"issue":"2","key":"22_CR14","doi-asserted-by":"crossref","first-page":"630","DOI":"10.1137\/S0097539704446232","volume":"37","author":"N Garg","year":"2007","unstructured":"Garg, N., K\u00f6nemann, J.: Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput. 37(2), 630\u2013652 (2007)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"22_CR15","first-page":"1093","volume":"244","author":"LG Ha\u010dijan","year":"1979","unstructured":"Ha\u010dijan, L.G.: A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR 244(5), 1093\u20131096 (1979)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"22_CR16","first-page":"187","volume-title":"Studies and Essays presented to R. Courant on his 60th Birthday","author":"F John","year":"1948","unstructured":"John, F.: Extremum problems with inequalities as subsidiary conditions. In: Friedrichs, K.O., Neugebauer, O.E., Stoker, J.J. (eds.) Studies and Essays presented to R. Courant on his 60th Birthday, pp. 187\u2013204. Interscience Publishers, New York (1948)"},{"issue":"4","key":"22_CR17","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","volume":"4","author":"N Karmarkar","year":"1984","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373\u2013395 (1984)","journal-title":"Combinatorica"},{"key":"22_CR18","unstructured":"Klee, V., Minty, G.: How good is the simplex algorithm? In: Inequalities, III (Proceedings Third Symposium, UCLA, 1969; Dedicated to the Memory of Theodore S. Motzkin), pp. 159\u2013175. Academic Press, New York (1972)"},{"key":"22_CR19","unstructured":"Lee, Y., Sinford, A.: A new polynomial-time algorithm for linear programming (2015). https:\/\/arxiv.org\/abs\/1312.6677"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"Madry, A.: Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, New York, NY, pp. 121\u2013130 (2010)","DOI":"10.1145\/1806689.1806708"},{"issue":"1","key":"22_CR21","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1137\/S1052623403422285","volume":"16","author":"Y Nesterov","year":"2005","unstructured":"Nesterov, Y.: Excessive gap technique in nonsmooth convex minimization. SIAM J. Optim. 16(1), 235\u2013249 (2005)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"22_CR22","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1137\/110848955","volume":"22","author":"J Pe\u00f1a","year":"2012","unstructured":"Pe\u00f1a, J., Soheili, N.: A smooth perceptron algorithm. SIAM J. Optim. 22(2), 728\u2013737 (2012)","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"22_CR23","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1007\/s10107-015-0860-y","volume":"155","author":"J Pe\u00f1a","year":"2016","unstructured":"Pe\u00f1a, J., Soheili, N.: A deterministic rescaled perceptron algorithm. Math. Program. 155(1\u20132), 497\u2013510 (2016)","journal-title":"Math. Program."},{"issue":"2","key":"22_CR24","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"SA Plotkin","year":"1995","unstructured":"Plotkin, S.A., Shmoys, D.B., Tardos, E.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2), 257\u2013301 (1995)","journal-title":"Math. Oper. Res."},{"key":"22_CR25","series-title":"Wiley-Interscience Series in Discrete Mathematics","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A.: Theory of linear and integer programming. Wiley-Interscience Series in Discrete Mathematics. John Wiley and Sons, Inc., New York (1986)"},{"key":"22_CR26","volume-title":"Approximation Algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Heidelberg (2001)"},{"key":"22_CR27","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The Design of Approximation Algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. University Press, Cambridge (2011)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59250-3_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T18:04:41Z","timestamp":1692813881000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}